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
Start by making sure you understand the definition provided in the problem for height of a tree (this is one of two common definitions). Then look 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 6-2, the heights of each subtree are:
- A: height 4
- B: height 1
- C: height 3
- D: height 2
- E: height 2
- F: height...
