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

Tree and Graph Problems

Most tree problems involve binary trees. You may occasionally encounter a graph problem, especially if the interviewer thinks you’re doing particularly well with easier problems.

Height of a Tree

PROBLEM The height of a tree (binary or not) is defined to be the maximum distance from the root node to any leaf node. The tree in Figure 5-2, for example, has a height of 4 because the path from A to F, G, or H involves four nodes. Write a function to calculate the height of an arbitrary binary tree.

Start by looking at some simple trees to see if there’s a way to think recursively about the problem. Each node in the tree corresponds to another subtree rooted at that node. For the tree in Figure 5-2, the heights of each subtree are:

• A: height 4
• B: height 1
• C: height 3
• D: height 2
• E: height 2
• F: height 1
• G: height 1
• H: height 1

Your initial guess might be that the height of a node is the sum of the height of its children because height A = 4 = height B + height C, but a quick test shows that this assumption is incorrect because height C = 3, but the heights of D and E add up to 4, not 3.

Look at the two subtrees on either side of a node. If you remove one of the subtrees, does the height of the tree change? Yes, but only if you remove the taller subtree. This is the key insight you need: The height of a tree equals the height of its tallest subtree plus one. This is a recursive definition that is easy to translate to code:

public static int treeHeight( ...