Start learning free

LESSON 413 OF 535 · BINARY TREES

Same Tree in C++: 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

    C++ · BINARY TREES

    Same Tree in C++, explained

    Problem overview

    The method isSameTree receives the roots of two binary trees, p and q, 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 TreeNode, with an int val and two TreeNode * fields, left and right.

    If both trees have root 1 with left child 2 and right child 3, the answer is true. If p is root 1 with a left child 2, and q is root 1 with a right child 2, the answer is false: the values match, but the 2 is in a different place. If p has root 1 with children 2 and 1, and q has root 1 with children 1 and 2, the shapes match and the left children hold different values, so the answer is false.

    Approach: compare the roots, then both pairs of subtrees

    A tree is its root together with its left and right subtrees, and those are trees too. So two trees are the same exactly when:

    1. their roots are both missing, or both present and holding the same value, and
    2. their left subtrees are the same, and
    3. their right subtrees are the same.

    That is a recursive definition, and it turns directly into a recursive function. Each call compares one node of p with the node in the same position of q, then hands the two pairs of children to itself. 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

    1. Both empty: if !p && !q, return true. Two empty trees are the same, and this test also ends the recursion when both sides step past a leaf at once.
    2. Exactly one empty: if !p || !q, return false. The case of both being empty already returned, so at this point one tree is empty and the other is not, and the shapes differ.
    3. Different values: if p->val != q->val, return false. Both nodes exist here, so reading their values is safe.
    4. Compare the children: return isSameTree(p->left, q->left) && isSameTree(p->right, q->right). The roots match, so the trees are the same exactly when both pairs of subtrees are.

    The order of the first two tests matters. The test for "exactly one empty" is only correct because the "both empty" case was handled before it.

    The solution in C++

    class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) {
            return true;
        }
        if (!p || !q) {
            return false;
        }
        if (p->val != q->val) {
            return false;
        }
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

    C++ details worth a closer look:

    • Null pointers in conditions. A null pointer is false and any other pointer is true, so !p is true exactly when p is nullptr. The tree's missing children are stored as null pointers (the lesson's TreeNode sets them to NULL).
    • Comparing pointers would be wrong. p == q asks whether the two variables point to the same node in memory. Two separate trees with equal contents have different addresses, so the function compares values with p->val != q->val instead.
    • Short-circuit &&. If the left subtrees differ, the call on the right subtrees never runs. The answer is already false.
    • Arrow versus dot. p and q are pointers to nodes, so fields are read with ->.

    Complexity

    Time: O(n), where n is the number of nodes in the smaller tree, at worst the number of nodes in either. Every call compares one pair of positions and makes at most two further calls, and a position is never compared twice. When the trees differ, the function can stop earlier.

    Space: O(h), where h is the height, for the recursion stack. A balanced tree has h around log n, and a chain has h equal to n. The constraints keep the depth at 400 levels or less.

    Edge cases and common mistakes

    • Both trees empty. isSameTree(nullptr, nullptr) returns true, from the first test.
    • One empty tree. An empty tree and a single node 0 are different, in either order. The second test returns false before any value is read.
    • Same values, different shape. Root 1 with left child 2 against root 1 with right child 2 gives false, because the left children are a node and an empty tree.
    • Same shape, different values. Two single nodes 7 and 8 give false.
    • Reading a value too early. Writing p->val != q->val before the null tests dereferences a null pointer when one tree is shorter, which is undefined behaviour.
    • Comparing only values. Visiting both trees and comparing the lists of values would miss differences in shape.

    Testing

    • p = [1, 2, 3] and q = [1, 2, 3] gives true.
    • p = [1, 2] and q = [1, NULL, 2] gives false.
    • p = [1, 2, 1] and q = [1, 1, 2] gives false.
    • Two empty trees give true.
    • An empty tree and the single node 0 give false, in either order.
    • The single nodes 7 and 7 give true, while 7 and 8 give false.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free