LESSON 414 OF 536 · BINARY TREES

Same Tree in JavaScript: 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 null 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,null,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 JavaScript, explained

Problem overview

The method isSameTree(p, q) receives the roots of two binary trees and returns true when they are the same tree: the same shape, and the same value in every position. Two empty trees are the same. The lesson provides the TreeNode constructor, with val, left and right (both children start as null).

The trees [1, 2, 3] and [1, 2, 3] are the same. The trees [1, 2] and [1, null, 2] hold the same values but are different, because the 2 is a left child in one and a right child in the other. The trees [1, 2, 1] and [1, 1, 2] have the same shape but different values in the left child.

Approach: compare the roots, then the subtrees

Two trees are the same when their roots hold the same value, their left subtrees are the same, and their right subtrees are the same. The second and third parts are the same question about smaller trees, so recursion fits. Each call looks at one pair of nodes, one from each tree, in the same position.

Three cases cover a pair of nodes:

both are empty: they match, and the recursion stops;
exactly one is empty: the shapes differ;
both exist: their values must match, and then both pairs of children must match.

Each pair of nodes is compared at most once, so the time is O(n), where n is the number of nodes.

Step by step

Both empty. If !p && !q, return true. !p is true when p is null. This is also where the recursion ends when both trees run out at the same moment.
Only one empty. If !p || !q, return false. The first check already handled "both empty", so here exactly one of them is empty.
Different values. If p.val != q.val, return false. Both nodes exist at this point, so reading val is safe.
Compare the children. Return this.isSameTree(p.left, q.left) && this.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 JavaScript

class Solution {
    isSameTree(p, q) {
        if (!p && !q) {
            return true;
        }
        if (!p || !q) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return this.isSameTree(p.left, q.left) && this.isSameTree(p.right, q.right);
    }
}

The JavaScript details worth knowing:

Truthiness of nodes. A null child is falsy and a node object is truthy, so !p is a short test for "no node". It doesn't depend on the node's val: a node holding 0 is still truthy.
!= against !==. The solution uses !=, which converts types before comparing, so 0 != "0" is false. With node values that are always numbers, it behaves like !==. In your own code, !== is the safer habit, because it never converts.
Short-circuit &&. When the left pair differs, the right pair is not compared, because the result is already false.
Order of the checks. The "both empty" check must come first. If the "one is empty" test went first, two empty trees would be called different.
Method calls. The recursion goes through this.isSameTree, because the function is a method of the class.

Complexity

Time: O(n). Each pair of positions is compared at most once, and the work per pair is constant.

Space: O(h), the height of the trees, for the recursion stack. The constraints keep it within 400 levels.

Edge cases and common mistakes

Two empty trees. [] and [] give true.
One empty tree. [] and [1] give false.
One tree is a prefix of the other. [1] and [1, 2] give false: the roots match, but one pair of children is a node against null.
Value 0. [0] and [0] give true. A test like if (p.val) would treat 0 as missing; the solution checks the nodes, not the values.
Same values, different shape. [1, 2] against [1, null, 2] gives false, because the left children are a node and null.
Checking only the values. Comparing the lists of values, for example from a traversal that skips missing children, can't tell those two trees apart.
Reading val too early. Reading p.val when p is null throws a TypeError. The first two checks prevent that.

Testing

[1, 2, 3] and [1, 2, 3] give true.
[1, 2] and [1, null, 2] give false.
[1, 2, 1] and [1, 1, 2] give false.
[] and [] give true.
[] and [1] give false.
[0] and [0] give true.

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

Start learning free