Height of a tree

The problem, simply

A binary tree is a family tree where every person has at most two children, a left one and a right one. The person at the top is the root. A person with no children is a leaf.

Find the height: the number of people on the longest walk from the root straight down to a leaf. An empty tree has height 0, and a tree with only the root has height 1.

Some books count the lines between people instead of the people. That number is always one less, so a tree of height 4 has 3 lines on its longest walk. Ask your interviewer which one they want.

A story to remember it

Picture it

Examples

Way 1: the simple way

Count the rows. Use a waiting line, a queue, the same way you read a tree row by row: put the root in, and each time you finish a whole row, add 1 to a counter.

1. Put the root in the waiting line. Set height = 0.
2. While the line is not empty, read its size. That many people make up the current row.
3. Take exactly that many from the front and put their children at the back.
4. Add 1 to height. Repeat.

import java.util.*;

class Solution {
    public int height(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> line = new ArrayDeque<>();
        line.add(root);
        int height = 0;
        while (!line.isEmpty()) {
            int size = line.size();           // people in this row
            for (int i = 0; i < size; i++) {
                TreeNode node = line.poll();
                if (node.left != null) line.add(node.left);
                if (node.right != null) line.add(node.right);
            }
            height++;                          // one more row finished
        }
        return height;
    }
}

How long it takes: every person joins the line once and leaves once, O(n). Extra room: the line holds one full row, so it is as big as the widest row w, O(w). In a full tree the bottom row has about n / 2 people.

Way 2: the clever way

Do what Grandma did. The height of a tree is 1 for yourself plus the taller of your two sides. An empty side has height 0.

1. If the node is empty, answer 0.
2. Ask the left child for its height. Ask the right child for its height.
3. Answer 1 + max(left, right).

The helpers that are waiting for answers sit on a pile, the call stack. The pile is never taller than the tree.

class Solution {
    public int height(TreeNode root) {
        if (root == null) return 0;              // empty side counts as 0
        int left = height(root.left);            // ask the left child
        int right = height(root.right);          // ask the right child
        return 1 + Math.max(left, right);        // me plus the taller side
    }
}

How long it takes: every person is asked exactly once, O(n). Extra room: the pile of waiting helpers is as tall as the tree, O(h). That is about log n for a bushy tree and n for a stick.

Watch out for

• Forgetting the empty tree. root == null must give 0 before you touch root.left.
• Taking left + right instead of max. Adding gives the number of nodes on a path through the node, which is a different problem (diameter).
• A stick shaped tree with a million nodes can overflow the call stack in Java. Way 1 never recurses, so it is safe there.

What interviewers ask next

• Find the diameter, the longest path between any two nodes. In the same walk, at each node also check left + right and keep the biggest.
• Check if a tree is balanced. Return the height, but return -1 as soon as two sides differ by more than 1, and pass the -1 up.
• Find the minimum depth, the closest leaf. Careful: a node with one empty side is not a leaf, so use the non-empty side there. Breadth first search can stop at the first leaf it meets.
• Do it without recursion and without a queue? You can use a stack of (node, depth) pairs and keep the biggest depth you see.

Remember this

Grown-up words: floors are levels, the bottom people are leaves, asking your children first and answering after is a postorder depth first search, the pile of waiting helpers is the recursion call stack, and the waiting line in Way 1 is a queue used for breadth first search.