Same Tree

The problem

A binary tree is made of nodes. Each node has a value, val, and two children, left and right; a missing child is null. You are given p and q, the top nodes of two trees. Either may be null, which means an empty tree. Return true if the two trees are the same: they have the same shape, and nodes in the same position hold the same value. Otherwise return false. Left and right are different positions, so a left child never matches a right child. Two empty trees are the same.

What to write

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

function solve(p: TreeNode | null, q: TreeNode | null): boolean

Input
p = {"val":1,"left":{"val":2,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}
q = {"val":1,"left":{"val":2,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}

Output
true

Input
p = {"val":1,"left":{"val":2,"left":null,"right":null},"right":null}
q = {"val":1,"left":null,"right":{"val":2,"left":null,"right":null}}

Output
false

Constraints

Nodes use {val, left, right}; either tree may be empty.

Hints

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

1. Hint 1: Use the constraints

   Either tree may be empty, so p or q can be null, or both. Shape counts as much as values: a node must sit in the same place in both trees. Before anything else, be sure what the answer is when both are null, and when only one is null.

2. Hint 2: Ask a smaller question

   Suppose the two roots hold the same value. What else must be true before you can call the trees the same? Try it on example 2, where both trees hold a 1 and a 2.

3. Hint 3: Name the pattern

   Once the roots match, the same question comes back for the two left children and for the two right children. So the function can call itself on each pair: that is recursion. The function's promise: given any two nodes, say whether the trees that start there are the same. A pair's answer comes from its children's answers: postorder tree recursion. Read the lesson on postorder tree recursion.

4. Hint 4: State the invariant

   The function always holds two nodes from the same position in their trees. The trees that start there are the same exactly when both nodes are missing, or both are there, hold equal values, and have the same trees starting at their left children and at their right children.

5. Hint 5: Sketch the pseudocode

   If both nodes are null, return true. If only one is null, return false. If their values differ, return false. Otherwise return true only when the function says the two left children are the same and the two right children are the same.

Solution

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

Approach

Compare corresponding nodes recursively. Missing nodes must match on both sides.

The slow way

Write out the values of each tree from the top down and compare the two lists. It is wrong, because a list of values forgets the shape. In example 2 both trees give the list 1, 2, although the 2 is a left child in one tree and a right child in the other.

The insight

A child with everything below it is called a subtree. Two trees with a root each are the same exactly when the roots hold the same value, the left subtrees are the same and the right subtrees are the same. The last two are the same question about smaller trees, so the function can ask itself, walking down both trees in step.

Step by step

1. Two missing nodes match: both trees end here. Both trees stop at the same place, so there is nothing left that could differ. This is the smallest case, and it is what ends the calls on a branch where the two trees agree.
2. One missing node means the shapes differ. This line is reached only when the two are not both missing. If one is missing now, one tree has a node where the other has nothing, and no value can repair that.
3. Two nodes with different values do not match. Both nodes are there, so their values can be read safely. One pair of unequal values is enough to make the whole trees different, so the answer is false at once.
4. Otherwise both pairs of children must match too. The two nodes agree, but the trees below them may still differ. The function calls itself, which is called recursion, and promises, for any two nodes, whether the trees that start there are the same.

The same numbered steps are the comments in each solution.

function solve(p, q) {
  // 1. Two missing nodes match: both trees end here
  if (!p && !q) return true;
  // 2. One missing node means the shapes differ
  if (!p || !q) return false;
  // 3. Two nodes with different values do not match
  if (p.val !== q.val) return false;
  // 4. Otherwise both pairs of children must match too
  return solve(p.left, q.left) && solve(p.right, q.right);
}

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };
function solve(p: TreeNode | null, q: TreeNode | null): boolean {
  // 1. Two missing nodes match: both trees end here
  if (!p && !q) return true;
  // 2. One missing node means the shapes differ
  if (!p || !q) return false;
  // 3. Two nodes with different values do not match
  if (p.val !== q.val) return false;
  // 4. Otherwise both pairs of children must match too
  return solve(p.left, q.left) && solve(p.right, q.right);
}

def solve(p, q):
    # 1. Two missing nodes match: both trees end here
    if p is None and q is None:
        return True
    # 2. One missing node means the shapes differ
    if p is None or q is None:
        return False
    # 3. Two nodes with different values do not match
    if p.val != q.val:
        return False
    # 4. Otherwise both pairs of children must match too
    return solve(p.left, q.left) and solve(p.right, q.right)

Example 1, traced

Input
p = {"val":1,"left":{"val":2,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}
q = {"val":1,"left":{"val":2,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}

Output
true

Why it works

The function compares the two nodes at one position and then every position below it. The function returns true only if no position has a node in one tree and nothing in the other, and no position holds two different values. That is what being the same means. A matching pair answers only after the pairs below it, which is what postorder means.

Time and space

Time O(n), extra space O(h). Each call checks one position in the two trees with constant work, and no position is checked twice: O(n) time for trees of n nodes. The unfinished calls form a chain from the roots down, one per level: O(h) on the call stack for trees with h levels.

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

• Check for missing nodes before you read a value. Every branch ends at missing children, and reading the value of null stops the program with an error.
• Two missing nodes are a match, not a difference. If the function returns false whenever it meets null, it returns false for every input, even two identical trees, because their branches all end at pairs of missing children.
• Do not compare the two nodes themselves with an equals sign. That asks whether they are one and the same object, so two separate trees with equal contents come out different. Compare their values.

Pattern

Postorder tree recursion. Builds on Maximum Depth of Binary Tree.

Keep going