2009-10-28

Post date: Nov 3, 2009 6:01:26 PM

Binary search tree in C. See bst.c attached below. Several points to note:

• We're writing recursive functions. Base case (terminal case) is when the tree reaches a NULL pointer. The recursion makes progress towards the base case because every time we make a recursive call, we're one node closer to a NULL pointer. We can assume this is the case because tree pointers are acyclic. If we have cyclic pointers (it wouldn't be a tree anymore), our recursive function may not terminate.
• find() takes a node and recursively calls find on either the left or right child depending on the key. If key is smaller than what's stored at node, we look into the left child. If key is greater, we look into the right child. Otherwise the key is equal to the one stored at the node, and we've found the node we're looking for. Initially, find() is called on the root of the tree. Notice that find() is tail recursive.
• insert() is a bit different. Ideally it should just return void and modify the tree transparently, but the pointer we want to modify resides in the parent of the current node. For now, we make insert() return the new updated subtree to the caller, which knows the parent and will perform the update. Notice that insert() is not tail recursive. We'll see a different way to write insert() next time.