Trees

A binary tree is a set of nodes where each node has a value and at most two children, a left one and a right one. The top node is the root, and nodes with no children are leaves. The depth of a node is how far it is from the root; the height of a tree is the number of levels on its longest root-to-leaf path. Interviewers ask tree questions because they test recursion (a function calling itself on a smaller input; see Recursion and backtracking) cleanly: almost every answer is "solve the two subtrees, then combine". A subtree is a node together with everything below it. On the problem pages, trees are written level by level, with null where a child is missing: [4, 2, 6, 1, 3, 5] is the tree used below.

The pattern behind most tree problems

Answer the question for the left subtree, answer it for the right subtree, and combine the two answers at the current node. The empty tree is the base case (the smallest input, answered directly). Height is 1 + the larger child height: in the tree below, the leaves have height 1, nodes 2 and 6 have height 2, and the root has height 3. "Are two trees the same?" is: roots equal, left subtrees the same, right subtrees the same. The diameter and the maximum path sum add one twist: the function returns one thing to its parent (the best downward path) while it updates a separate best answer (the best path that bends at this node).

Four ways to walk a tree

Depth-first walks go all the way down one branch before the next. They differ only in when they record the node: preorder records it before its children (useful for copying a tree), inorder between the left and right child, and postorder after both children (useful when a node needs its children's answers first, as for height). Breadth-first, or level order, uses a queue: before each round, note how many nodes are in the queue; that many nodes form the current level.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static void preorder(TreeNode node, List<Integer> out) {
        if (node == null) {
            return;
        }
        out.add(node.val);
        preorder(node.left, out);
        preorder(node.right, out);
    }

    static void inorder(TreeNode node, List<Integer> out) {
        if (node == null) {
            return;
        }
        inorder(node.left, out);
        out.add(node.val);
        inorder(node.right, out);
    }

    static void postorder(TreeNode node, List<Integer> out) {
        if (node == null) {
            return;
        }
        postorder(node.left, out);
        postorder(node.right, out);
        out.add(node.val);
    }

    static List<List<Integer>> levels(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            for (int k = queue.size(); k > 0; k--) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            out.add(level);
        }
        return out;
    }

    static int height(TreeNode node) {
        return node == null ? 0 : 1 + Math.max(height(node.left), height(node.right));
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4,
                new TreeNode(2, new TreeNode(1, null, null), new TreeNode(3, null, null)),
                new TreeNode(6, new TreeNode(5, null, null), null));
        List<Integer> pre = new ArrayList<>();
        List<Integer> in = new ArrayList<>();
        List<Integer> post = new ArrayList<>();
        preorder(root, pre);
        inorder(root, in);
        postorder(root, post);
        System.out.println("preorder:  " + pre);
        System.out.println("inorder:   " + in);
        System.out.println("postorder: " + post);
        System.out.println("levels:    " + levels(root));
        System.out.println("height:    " + height(root));
    }
}

preorder:  [4, 2, 1, 3, 6, 5]
inorder:   [1, 2, 3, 4, 5, 6]
postorder: [1, 3, 2, 5, 6, 4]
levels:    [[4], [2, 6], [1, 3, 5]]
height:    3

from collections import deque


class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def preorder(node, out):
    if node is None:
        return
    out.append(node.val)
    preorder(node.left, out)
    preorder(node.right, out)


def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)


def postorder(node, out):
    if node is None:
        return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.val)


def levels(root):
    out = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        out.append(level)
    return out


def height(node):
    return 0 if node is None else 1 + max(height(node.left), height(node.right))


root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6, TreeNode(5)))
pre, ino, post = [], [], []
preorder(root, pre)
inorder(root, ino)
postorder(root, post)
print("preorder: ", pre)
print("inorder:  ", ino)
print("postorder:", post)
print("levels:   ", levels(root))
print("height:   ", height(root))

preorder:  [4, 2, 1, 3, 6, 5]
inorder:   [1, 2, 3, 4, 5, 6]
postorder: [1, 3, 2, 5, 6, 4]
levels:    [[4], [2, 6], [1, 3, 5]]
height:    3

Binary search trees

A binary search tree (BST) adds a rule: every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger. Search and insert then walk a single path: compare, go left or right, repeat. To insert 7 into the tree above you go right at 4 and right at 6, and 7 becomes the right child of 6. An inorder walk lists a BST's values in ascending order, as the output shows, which is a quick way to check one.

Validating a BST is a classic trap. Checking each node only against its own children is not enough; every node must respect all its ancestors (the nodes on the path from it up to the root). Pass down the range of allowed values instead, and start that range outside the 32-bit limits, not at them.

The work for search and insert depends on the height. A balanced tree of n nodes has a height of about log n; a tree built by inserting sorted values becomes a chain with height n. Recursive code on a chain goes n calls deep, which can exhaust the call stack, so offer a loop with your own stack when the tree can be very deep.

How to answer in an interview

Say what your function returns for an empty tree, then what it returns for a node given its two children's answers. Name the walk you use and why ("postorder, because a node needs its children's heights first"). Trace a three-node tree, then give the cost: each node is visited once, so O(n) time, and O(h) space for the recursion on a tree of height h.

Common mistakes

• Forgetting the empty tree. Decide what it returns before you write anything else.
• Assuming the answer passes through the root (diameter, maximum path sum, lowest common ancestor).
• Comparing values only, when the shape matters too (same tree, symmetric tree).
• Starting a "best so far" at 0 when all values can be negative.

Recap

Solve the left and right subtrees, then combine. Pick the walk by when you need the node: before its children, between them, after them, or level by level. In a BST, use the ordering rule to walk one path, and check every node against its ancestors.