Subtree of Another Tree

The problem

root and subRoot are the top nodes of two binary trees. Either can be null, which means an empty tree. Each node has a number val and up to two children, left and right; a missing child is null. A subtree is a node together with every node below it. Return true if the first tree has a subtree that is exactly the second tree: the same shape, with the same value in every position. Otherwise return false. When subRoot is null, return true: an empty tree counts as found.

What to write

type TreeNode = {val:number;left:TreeNode|null;right:TreeNode|null};

function solve(root: TreeNode | null, subRoot: TreeNode | null): boolean

Input
root = {"val":3,"left":{"val":4,"left":{"val":1,"left":null,"right":null},"right":{"val":2,"left":null,"right":null}},"right":{"val":5,"left":null,"right":null}}
subRoot = {"val":4,"left":{"val":1,"left":null,"right":null},"right":{"val":2,"left":null,"right":null}}

Output
true

Input
root = {"val":3,"left":{"val":4,"left":{"val":1,"left":null,"right":null},"right":{"val":2,"left":{"val":0,"left":null,"right":null},"right":null}},"right":{"val":5,"left":null,"right":null}}
subRoot = {"val":4,"left":{"val":1,"left":null,"right":null},"right":{"val":2,"left":null,"right":null}}

Output
false

Constraints

Both inputs are binary trees represented by {val, left, right}; an empty subRoot matches.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   A copy of subRoot can start at any node of root, not only at the top. It must also be complete: that node may not have extra nodes below it that subRoot lacks. Either tree can be empty, so decide those two cases first.

2. Hint 2: Ask a smaller question

   Point at one node of root. How would you check, by hand, that this node and everything below it are exactly subRoot? And if they are not, where could a copy still be?

3. Hint 3: Name the pattern

   A tree contains a copy of subRoot if the copy starts at its top node, or the left child's subtree contains one, or the right child's subtree does. So a function can answer for a node by calling itself on the two children. Building a node's answer from its children's answers is postorder tree recursion. Read the lesson on postorder tree recursion.

4. Hint 4: State the invariant

   A call on a node answers for the whole subtree that starts there: does that subtree contain an exact copy of subRoot? The test at one node walks both trees together and says yes only when every pair of nodes agrees. A missing child agrees only with another missing child.

5. Hint 5: Sketch the pseudocode

   same(a, b): if either node is missing, return whether both are missing. Otherwise return: the values are equal, and same(left children), and same(right children). solve: if subRoot is empty, return true. If root is empty, return false. Return same(root, subRoot), or solve(left child, subRoot), or solve(right child, subRoot).

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

At each root candidate, compare the entire subtree. Otherwise continue searching both child subtrees.

The slow way

Write each tree's values in a row: a node, then everything under its left child, then everything under its right child. Look for subRoot's row inside root's row. It is tempting but wrong, because a row of values forgets the shape. In example 2 the rows are 3, 4, 1, 2, 0, 5 and 4, 1, 2. The second sits inside the first, yet the answer is false.

The insight

A copy of subRoot has to start at some node of root. So ask one yes-or-no question at every node: is the subtree here exactly subRoot? That question is the Same Tree problem: walk both trees together, position by position, and a missing child must face a missing child.

Step by step

1. To compare two trees: two missing nodes match, one alone does not. Two missing nodes in the same position mean both trees end here, which agrees. If only one is missing, one tree has a node that the other lacks.
2. Otherwise the values must be equal and both pairs of children match. Equal values at the top are not enough. The same test runs on the two left children and on the two right children, and so on down, until a pair disagrees or both trees end.
3. An empty subRoot counts as found in any tree. The problem defines it that way. Checking it first means that from here on subRoot has at least one node.
4. An empty root has no node where a copy could start. subRoot has a node, and an empty tree has none to match it. This is also where the search ends below a node with a missing child.
5. The copy starts at this node, or somewhere under one of its children. Those are the only places a copy can be. If the comparison at this node fails, the same search runs on the left child and, if that finds nothing, on the right child.

The same numbered steps are the comments in each solution.

function solve(root, subRoot) {
  function same(a, b) {
    // 1. To compare two trees: two missing nodes match, one alone does not
    if (!a && !b) return true;
    if (!a || !b) return false;
    // 2. Otherwise the values must be equal and both pairs of children match
    if (a.val !== b.val) return false;
    return same(a.left, b.left) && same(a.right, b.right);
  }
  // 3. An empty subRoot counts as found in any tree
  if (!subRoot) return true;
  // 4. An empty root has no node where a copy could start
  if (!root) return false;
  // 5. The copy starts at this node, or somewhere under one of its children
  return (
    same(root, subRoot) ||
    solve(root.left, subRoot) ||
    solve(root.right, subRoot)
  );
}

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };
function solve(root: TreeNode | null, subRoot: TreeNode | null): boolean {
  function same(a: TreeNode | null, b: TreeNode | null): boolean {
    // 1. To compare two trees: two missing nodes match, one alone does not
    if (!a && !b) return true;
    if (!a || !b) return false;
    // 2. Otherwise the values must be equal and both pairs of children match
    if (a.val !== b.val) return false;
    return same(a.left, b.left) && same(a.right, b.right);
  }
  // 3. An empty subRoot counts as found in any tree
  if (!subRoot) return true;
  // 4. An empty root has no node where a copy could start
  if (!root) return false;
  // 5. The copy starts at this node, or somewhere under one of its children
  return (
    same(root, subRoot) ||
    solve(root.left, subRoot) ||
    solve(root.right, subRoot)
  );
}

def solve(root, subRoot):
    def same(a, b):
        # 1. To compare two trees: two missing nodes match, one alone does not
        if not a and not b:
            return True
        if not a or not b:
            return False
        # 2. Otherwise the values must be equal and both pairs of children match
        if a.val != b.val:
            return False
        return same(a.left, b.left) and same(a.right, b.right)

    # 3. An empty subRoot counts as found in any tree
    if not subRoot:
        return True
    # 4. An empty root has no node where a copy could start
    if not root:
        return False
    # 5. The copy starts at this node, or somewhere under one of its children
    return (
        same(root, subRoot)
        or solve(root.left, subRoot)
        or solve(root.right, subRoot)
    )

Example 2, traced

Input
root = {"val":3,"left":{"val":4,"left":{"val":1,"left":null,"right":null},"right":{"val":2,"left":{"val":0,"left":null,"right":null},"right":null}},"right":{"val":5,"left":null,"right":null}}
subRoot = {"val":4,"left":{"val":1,"left":null,"right":null},"right":{"val":2,"left":null,"right":null}}

Output
false

Why it works

The search asks at every node of root whether the subtree there is exactly subRoot, because it moves on to both children whenever the answer is no. The comparison says yes only if every value agrees and every missing child faces a missing child. So a yes is a real copy, and no copy is skipped.

Time and space

Time O(n m), extra space O(h). A comparison can start at each of the n nodes of root and walk all m nodes of subRoot: O(n m) time. The unfinished calls lie along one path down root, so the space is O(h), where the height h counts the nodes on the longest path down root.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• The comparison must not stop when subRoot runs out of nodes: the other tree has to run out at the same place. Otherwise example 2 returns true, although the 2 in root has a child that subRoot lacks.
• A failed comparison at one node is not the final answer. The copy can start lower down, so the search has to go on into both children. With only the top node compared, example 1 returns false.
• Check for a missing node before you read its value. Whenever two nodes match, the comparison goes on to their children, missing ones included, and reading the value of a missing node stops the program with an error.

Pattern

Postorder tree recursion. Builds on Same Tree.

Keep going