Same Tree

Easy
1862.

Same Tree

Same Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Microsoft and Bloomberg interviews.

You are given the roots p and q of two binary trees. Return true if the two trees are identical — the same shape, with equal values in every corresponding node — and false otherwise.

Example 1

Input
p = [1,2,3], q = [1,2,3]
Output
true

Example 2

Input
p = [1,2], q = [1,null,2]
Output
false
Explanation
Both trees hold 1 and 2, but in `p` the 2 is a left child and in `q` a right child — the shapes differ.

Example 3

Input
p = [1,2,1], q = [1,1,2]
Output
false
Explanation
Same shape, but the left children hold 2 and 1.

Constraints

  • The number of nodes in both trees is in the range [0, 100]
  • -10^4 <= Node.val <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Same Tree — Solution in Python, Java & C++

Same Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Microsoft.

Same Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Microsoft and Bloomberg interviews.

Problem statement

You are given the roots p and q of two binary trees. Return true if the two trees are identical — the same shape, with equal values in every corresponding node — and false otherwise.

Example 1

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2

Input: p = [1,2], q = [1,null,2]
Output: false
Explanation: Both trees hold 1 and 2, but in `p` the 2 is a left child and in `q` a right child — the shapes differ.

Example 3

Input: p = [1,2,1], q = [1,1,2]
Output: false
Explanation: Same shape, but the left children hold 2 and 1.

Constraints

  • The number of nodes in both trees is in the range [0, 100]
  • -10^4 <= Node.val <= 10^4

Hints for Same Tree

  1. Hint 1

    Two empty trees are identical; an empty tree and a non-empty one are not.

  2. Hint 2

    Two non-empty trees are identical exactly when their roots hold the same value and their left subtrees are identical and their right subtrees are identical.

  3. Hint 3

    That sentence is the whole recursion — compare, then recurse on the left pair and the right pair, stopping at the first mismatch.

How to solve Same Tree

Identity is defined recursively: equal roots, identical left subtrees, identical right subtrees. Walk both trees in lock-step and stop at the first difference in shape or value.

Approach

  1. If both nodes are null, return true.
  2. If exactly one is null, return false — the shapes differ.
  3. If the values differ, return false.
  4. Otherwise return same(p.left, q.left) && same(p.right, q.right).

Why it works

Each call compares one pair of positions that occupy the same place in both trees. Every position present in either tree is reached, because the recursion only stops early on a mismatch (which already decides the answer) or when both sides are empty (nothing left to compare there).

Complexity

  • Time — O(min(n, m)) — the walk stops at the smaller tree's boundary or the first mismatch
  • Space — O(h) recursion depth

Pitfalls

  • Comparing one traversal list is not enough: [1,2] and [1,null,2] have the same preorder [1,2] but different shapes.
  • Check the null cases before reading .val.

Reference solution

Python

from typing import Optional

def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    if p is None or q is None:
        return p is q
    return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

Java

public static boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null || q == null) return p == q;
    return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

C++

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p || !q) return p == q;
    return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

JavaScript

var isSameTree = function(p, q) {
    if (p === null || q === null) return p === q;
    return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)