Solving Tree-related Problems

A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root.

There are two types of trees that are frequently asked in the interview:

• Binary Tree: a tree in which each node has up to two children
• Binary Search Tree: a binary tree in which every node fits a specific ordering property: all left descendants ≤ n < all right descendants.

Most tree-related problems boil down to tree traversals.

Complete Traversal

Preorder, inorder, postorder, and level order are all complete traversal, meaning normally we visit every node of the tree in a certain order.

We can use it to solve problems that ask us to verify/compute the properties of a given binary tree. This type of problem generally starts with “Given a binary tree, check/get [some properties of the tree]”. We need to identify the property and verify/compute it on the root node and all its subtrees recursively.

• Given a binary tree, determine if it is height-balanced.
• Given a binary tree, find its maximum depth.
• Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

Another type of problem asks us to traversal the tree and perform some action on the leaf nodes. Normally, I solve it by preorder traversal + backtracking.

• Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Some problems ask us to manipulate the tree structure which can be done while traversing the tree. I typically try postorder first, the thought is assuming the left and right subtree are at the desired state, what do I need to do with the root node?

• Invert a binary tree.
• Flatten Binary Tree to Linked List

When it comes to BST, try inorder traversal first, as its result is ordered.

• Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure.

The level order traversal to me is like a special case of BFS.

Partial Traversal

There are a limited number of problems are solved by visiting partial of the tree. Usually, it’s not an ordinary tree, it’s a tree with special properties that are critical to solving the problem. It gives you the feeling that you need to find the searching criteria and narrow down/determine which subtree to visit next. Consider the two problems below:

[Problem 1] Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. For example, the LCA of node 2 and node 8 is 6.

What’s the special property of a BST?

Every node fits a specific ordering property: all left descendants ≤ n < all right descendants.

We can use this property to narrow down the search space. If the root’s value is bigger than max(p, q), search the left subtree. Otherwise, search the right subtree.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return null;
    }
    int min = Math.min(p.val, q.val);
    int max = Math.max(p.val, q.val);
    
    if (root.val >= min && root.val <= max) {
        return root;
    }
    
    return root.val > max ? lowestCommonAncestor(root.left, p, q) : lowestCommonAncestor(root.right, p, q);
}

[Problem 2] Given a complete binary tree, count the number of nodes. For example, the number of nodes of the tree below is 6.

Apparently, this problem expects us to use the special properties of the complete binary tree instead of performing a complete traversal and count.

What’s the special property of a complete binary tree?

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

Again, we can use this special property to narrow down the search space.

The height of a complete binary tree is the length from root to the left-most leaf node and can be calculated as below

private int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return getHeight(root.left) + 1;
}

We can calculate the height of the left and right subtrees, namely h1 and h2. If they are the same, it means the left subtree is a complete binary tree of height h1, we can simply calculate the number of nodes in the left subtree as “2^h1-1” and recursively count the right subtree, there is no need to traverse to the left subtree. Otherwise, it means the right subtree is a complete binary tree of h2, we can calculate the number of nodes of it as “2^h2-1” and recursively count the left subtree.

public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }
    
    int lh = getHeight(root.left);
    int rh = getHeight(root.right);
    
    // this means we can take the whole left subtree and the root
    // we recursively need to countNodes(root.right);
    if (lh == rh) {
        return (1 << lh) + countNodes(root.right);
    }
    
    // otherwise, it means we can take right subtree and the root
    // we resursively need to countNodes(root.left);
    return (1 << rh) + countNodes(root.left);
}

As you can see, both questions only partially visit the tree.