Start learning free

LESSON 418 OF 540 · BINARY TREES

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

Practice O(n) Read the full explanation

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, 104].
  • Each node value is between -104 and 104.
  • 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
    Ctrl + Enter to check

    TYPESCRIPT · BINARY TREES

    Same Tree in TypeScript, explained

    Problem overview

    The method isSameTree(p, q) receives the roots of two binary trees and returns true if they are the same tree. Two 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 lesson provides the TreeNode type: a node has a number val and two children, left and right, each a node or 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 in the first the 2 is the left child of the root and in the second it is the right child, so they differ. The trees [1,2,1] and [1,1,2] have the same shape, but their left children hold 2 and 1, so they differ too.

    Approach: compare the roots, then the subtrees

    A tree is made of a root and two smaller trees, and "the same" splits the same way: 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. That is a recursive definition, and it translates directly into a recursive function. The recursion ends when it reaches missing children, so there are three base cases to decide before comparing anything:

    • both nodes are missing: nothing differs here, so the answer is true;
    • exactly one is missing: the shapes differ, so the answer is false;
    • both exist but hold different values: false.

    Only when all three tests are passed do the subtrees need to be compared. Each pair of nodes is looked at at most once, so the running time is linear.

    Step by step

    1. Both empty. If !p && !q, return true. !p is true when p is null. This test also ends the recursion when both trees run out at the same moment.
    2. Only one empty. If !p || !q, return false. The case of two empty trees has already returned, so here exactly one tree is empty and the other is not.
    3. Different values. If p.val != q.val, return false. Both nodes exist at this point, so reading val is safe.
    4. Compare the subtrees. 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 TypeScript

    class Solution {
    isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
        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);
    }
}

    Details worth knowing:

    • Truthiness of nodes. A TreeNode object is always truthy, even when its val is 0, so !p is true only when p is null (or undefined). It tests the node, not its value. For two trees that each hold just a node with value 0, the function returns true, not false.
    • != and !==. The reference compares the values with !=. For two numbers it gives the same result as !==, because no conversion is needed. != would convert if the types differed: 1 != "1" is false, while 1 !== "1" is true. With number fields that cannot arise, but !== is the safer habit.
    • Short-circuit &&. When the left subtrees already differ, the right ones are not compared, since the answer is already false.
    • The same tree twice. Passing a tree as both arguments works, and gives true: the function never changes the trees.
    • Types are erased. TreeNode | null helps the compiler and disappears in the JavaScript output. It checks nothing at run time.

    Complexity

    Time: O(n), where n is the number of nodes in the smaller tree, or in either when they are the same. Each pair of nodes is compared at most once, with constant work per pair, and the recursion stops at the first difference.

    Space: O(h) for the recursion, where h is the height of the trees: up to the 400 levels the constraints allow, or O(log n) for balanced trees.

    Edge cases and common mistakes

    • Two empty trees. [] and [] give true. One empty and one not, such as [] and [1], gives false.
    • Same values, different shape. [1,2] against [1,null,2] is false. Comparing the values in level order or sorted order would miss this, which is why the left and right children are compared separately.
    • Same shape, different values. [1,2,1] against [1,1,2] is false.
    • Different sizes. [1,2,3] against [1,2] is false: when the recursion reaches the missing right child, only one side has a node.
    • Reading val too early. Reading p.val before the null tests would throw a TypeError on a missing node. The order of the three tests matters.
    • Testing the value for truthiness. Writing something like if (!p.val) would treat 0 as missing. Values can be 0 or negative, so the tests are on the nodes.

    Testing

    • p = [1,2,3], q = [1,2,3] gives true.
    • p = [1,2], q = [1,null,2] gives false.
    • p = [1,2,1], q = [1,1,2] gives false.
    • p = [], q = [] gives true.
    • p = [], q = [1] gives false.
    • p = [0], q = [0] gives true.
    • p = [1,2,3,4], q = [1,2,3,5] gives false.
    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free