6.3 Discussion and Exercises

Binary trees have been used to model relationships for literally thousands of years. One reason for this is that binary trees naturally model (pedigree) family trees. These are the family trees in which the root is a person, the left and right children are the person's parents, and so on, recursively. In more recent centuries binary trees have also been used to model species-trees in biology, where the leaves of the tree represent extant species and the internal nodes of the tree represent speciation events in which two populations of a single species evolve into two separate species.

Binary search trees appear to have been discovered independently by several groups in the 1950s [41, Section 6.2.2]. Further references to specific kinds of binary search trees are provided in subsequent chapters.

Exercise 6..1   Write a non-recursive variant of the $\mathtt{size2()}$ method, $\mathtt{size(u)}$, that computes the size of the subtree rooted at node $\mathtt{u}$.

Exercise 6..2   Write a non-recursive method, $\mathtt{height2(u)}$, that computes the height of node $\mathtt{u}$ in a binary search tree.

Exercise 6..3   A pre-order traversal of a binary tree is a traversal that visits each node, $\mathtt{u}$, before any of its children. An in-order traversal visits $\mathtt{u}$ after visiting all the nodes in $\mathtt{u}$'s left subtree but before visiting any of the nodes in $\mathtt{u}$'s right subtree. A post-order traversal visits $\mathtt{u}$ only after visiting all other nodes in $\mathtt{u}$'s subtree.

Write non-recursive functions $\mathtt{nextPreOrder(u)}$, $\mathtt{nextInOrder(u)}$, and $\mathtt{nextPostOrder(u)}$ that return the node that follows $\mathtt{u}$ in a pre-order, in-order, or post-order traversal, respectively.

Exercise 6..4   Describe a sequence of $\mathtt{n}$ operations on an initially empty BinarySearchTree that results in a tree of height $\ensuremath{\mathtt{n}}-1$.

Exercise 6..5   Design and implement a version of BinarySearchTree in which each node, $\mathtt{u}$, maintains values $\mathtt{u.size}$ (the size of the subtree rooted at $\mathtt{u}$), $\mathtt{u.depth}$ (the depth of $\mathtt{u}$), and $\mathtt{u.height}$ (the height of the subtree rooted at $\mathtt{u}$).

These values should be maintained, even during the $\mathtt{add(x)}$ and $\mathtt{remove(x)}$ operations, but this should not increase the cost of these operations by more than a constant factor.