Programming Interviews Exposed: Secrets to Landing Your Next Job, Second Edition

5.3. Binary Tree Problems

As previously mentioned, binary trees are the mostly commonly used forms of trees. Here are some typical problems regarding binary trees.

5.3.1. Preorder Traversal

NOTE

Informally, a preorder traversal involves walking around the tree in a counterclockwise manner starting at the root, sticking close to the edges, and printing out the nodes as you encounter them. For the tree shown in Figure 5-6, the result is 100, 50, 25, 75, 150, 125, 110, 175. Perform a preorder traversal of a binary search tree, printing the value of each node.

Figure 5.6. Figure 5-6

To discover an algorithm for printing out the nodes in the correct order, you should examine what happens as you print out the nodes. You go to the left as far as possible, come up the tree, go one node to the right, and then go to the left as far as possible, come up the tree again, and so on. The key is to think in terms of subtrees.

The two largest subtrees are rooted at 50 and 150. Note one very important thing about the nodes in these two subtrees: All of the nodes in the subtree rooted at 50 are printed out before any of the nodes in the subtree rooted at 150. In addition, the root node for each subtree is printed out before the rest of the subtree. Generally, for any node in a preorder traversal, you would print the node itself, followed by the left subtree, and then the right subtree. If you ...