# 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( ...``

Get Programming Interviews Exposed: Secrets to Landing Your Next Job, 3rd Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.