LESSON 418 OF 540 · BINARY TREES

Same Tree in Go: Recursive Comparison in O(n)

Given the roots of two binary trees, p and q, return true if they are the same tree, and false otherwise.

Two binary trees are the same when they have exactly the same shape and every node holds the same value as the node in the same place in the other tree. Two empty trees are the same.

The trees below are written in level order (top to bottom, left to right), with nil for a missing child.

Example 1:

     p          q
     1          1
    / \        / \
   2   3      2   3

Input: p = [1,2,3], q = [1,2,3]
Output: true
Explanation: Both trees have the root 1, with 2 as its left child and 3 as its right child.

Example 2:

     p          q
     1          1
    /            \
   2              2

Input: p = [1,2], q = [1,nil,2]
Output: false
Explanation: The trees hold the same values, but the 2 is the left child of the root in p and the right child in q.

Example 3:

     p          q
     1          1
    / \        / \
   2   1      1   2

Input: p = [1,2,1], q = [1,1,2]
Output: false
Explanation: The shapes match, but the left children hold different values: 2 in p and 1 in q.

Constraints:

The number of nodes in each tree is in the range [0, 10⁴].
Each node value is between -10⁴ and 10⁴.
Each tree is at most 400 levels deep.

Note:

Your algorithm should run in O(n) time, where n is the number of nodes, comparing each pair of nodes at most once.

STEP 1 OF 4

Guided

Ctrl + Enter to check

Same Tree in Go, explained

Problem overview

The function isSameTree receives the roots of two binary trees, p and q (the lesson provides TreeNode, with Val, Left and Right), and returns true when they are the same tree. That means the same shape, and the same value at every position. Two empty trees are the same.

Trees written in level order, with nil for a missing child, give these results:

p = [1, 2, 3] and q = [1, 2, 3] give true.
p = [1, 2] and q = [1, nil, 2] give false: the values are the same, but the 2 is the left child of the root in p and the right child in q.
p = [1, 2, 1] and q = [1, 1, 2] give false: the shapes match, but the left children hold 2 and 1.

Approach: compare the roots, then the subtrees

A tree is defined by its root value, its left subtree and its right subtree. So two trees are the same exactly when their roots hold the same value, their left subtrees are the same, and their right subtrees are the same. The two subtree questions have the same form as the original, which is what recursion needs.

Before comparing values, the function has to settle whether each node exists. There are four cases for a pair of positions: both empty, one empty, both present with different values, and both present with equal values. The first three give an answer at once. Only the last one needs to look deeper.

Each pair of nodes is compared at most once, so the time is O(n), where n is the number of nodes in the smaller tree, or either one when they match.

Step by step

Both are nil: if p == nil && q == nil, return true. Two empty trees are the same. This also stops the recursion when both sides step past a leaf together.
Only one is nil: if p == nil || q == nil, return false. The both-empty case has already returned, so exactly one tree is empty here, and the shapes differ.
The values differ: if p.Val != q.Val, return false. Both nodes exist at this point, so reading Val is safe.
Compare the children: return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right). The roots already match, so the trees are the same exactly when both pairs of subtrees are.

The solution in Go

func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}
	if p == nil || q == nil {
		return false
	}
	if p.Val != q.Val {
		return false
	}
	return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

Go details worth knowing:

Nil pointers mark missing nodes. A child that doesn't exist is a nil *TreeNode, and comparing a pointer with nil is how the function tells the cases apart. Reading p.Val on a nil pointer would panic, which is why the two nil tests come before the value test.
The order of the tests matters. The "one is nil" test relies on the "both are nil" test above it having returned already. Swapping them would make two empty trees answer false.
Short-circuit &&. If the left subtrees differ, the right ones are never compared, so a difference on the left ends the work early.
Pointer comparison is not enough. p == q would compare addresses: two separately built trees with identical content are different pointers. The function compares the contents, so it answers true for them.

Complexity

Time: O(n). Each pair of nodes is compared at most once, and each comparison takes constant time. The function stops early as soon as it finds a difference.

Space: O(h) for the recursion, where h is the height of the trees. The statement limits the depth to 400 levels.

Edge cases and common mistakes

Two empty trees. isSameTree(nil, nil) returns true.
One empty tree. nil against [1] returns false.
Same values, different shape. [1, 2] and [1, nil, 2] hold the same values, but the answer is false. Comparing the lists of values alone would miss this, which is why missing children count as part of the comparison.
One tree is a prefix of the other. [1, 2] against [1, 2, 3] returns false: at the right child, one side is nil and the other holds 3.
Single equal nodes. [7] against [7] returns true, and both children pairs are nil, which hit the first test.
Checking the value before the nil tests. It panics with a nil pointer dereference whenever the trees' shapes differ.

Testing

[1, 2, 3] and [1, 2, 3] give true.
[1, 2] and [1, nil, 2] give false.
[1, 2, 1] and [1, 1, 2] give false.
nil and nil give true.
nil and [1] give false.
[7] and [7] give true.
[1, 2] and [1, 2, 3] give false.

Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free