[prev] 41 [next]

Exercise 3: BSTree Operations

The files BSTree.h and BSTree.c contain an ADT for binary search trees.

Using these definitions, implement the following operations:

  • BSTree newBSTree() (create empty tree)
  • void dropBSTree(BSTree) (free memory for tree)
  • int BSTreeFind(BSTree,int) (search for value in tree)
  • int BSTreeDepth(BSTree) (compute depth of tree)
  • int BSTreeNodes(BSTree) (count #nodes in tree)
  • BSTree BSTreeInsert(BSTree,int) (insert value into tree)
Look at VisuAlgo first, for some ideas.

Most are best expressed recursively.  Base case?  Recursive case?

Note:   BSTreeFind() returns yes/no;   BSTreeInsert() ignores duplicates