Start learning free

LESSON 417 OF 539 · 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 when they are the same tree: exactly the same shape, and the same value in every position. Two empty trees are the same. The lesson provides the TreeNode class with the fields val, left and right.

    • [1, 2, 3] and [1, 2, 3] are the same.
    • [1, 2] and [1, null, 2] hold the same values but are different: the 2 is the left child in one tree and the right child in the other.
    • [1, 2, 1] and [1, 1, 2] have the same shape but different values: the left children are 2 and 1.

    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 two subtree questions are the same problem on smaller trees, so recursion fits. The recursion needs three situations to be settled before it goes deeper:

    • Both nodes are missing. Two empty trees are the same, so the answer is true. This is also where the recursion stops, when both sides step past a leaf together.
    • Exactly one node is missing. The shapes differ, so the answer is false.
    • Both nodes exist but hold different values. The answer is false.

    If none of those applies, the two roots match, and the trees are the same exactly when both pairs of subtrees are. Each pair of nodes is compared at most once, so the time is O(n).

    Step by step

    1. Both null: if p == null && q == null, return true.
    2. One null: if p == null || q == null, return false. The case of both being null was handled above, so here exactly one tree is empty and the other isn't.
    3. Different values: if p.val != q.val, return false. Both nodes exist at this point, so reading their values is safe.
    4. Recurse: return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right). When the left pair already differs, && skips the right pair.

    The solution in C#

    class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
    }
}

    The C# details worth knowing:

    • The order of the checks matters. The value test p.val != q.val comes after both null tests. If either node were null, reading val would throw a NullReferenceException.
    • Compare values, not references. TreeNode is a class, so p == q would ask whether both variables point to the same object, and two separately built trees never do. The solution compares the val fields and walks the structure.
    • null tests with ==. For a class without its own == operator, p == null simply checks that the reference is empty.
    • Short-circuit &&. The right-hand call runs only if the left-hand call returned true, which saves work on trees that differ early.

    Complexity

    Time: O(n), where n is the number of nodes, because each pair of nodes is compared at most once, with constant work per pair.

    Space: O(h), where h is the height of the tree, for the recursion. At most 400 levels deep here, so the default stack is enough. A degenerate chain of nodes would use O(n) stack.

    Edge cases and common mistakes

    • Both trees empty. The result is true, since both nodes are null at once.
    • One tree empty. With [1] and an empty tree, the result is false.
    • Same values, different shape. [1, 2] against [1, null, 2] returns false, because the left children are a node and null. Comparing the values in level order and ignoring the shape would miss this.
    • Same shape, different values. [1, 2, 1] against [1, 1, 2] returns false at the left children.
    • Checking only one null. A test such as p == null alone, followed by q.val, crashes when q is the null one.
    • Comparing the nodes with ==. This tests identity, not equality of content.

    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 = [1], q = [] gives 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