DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Same Tree

easyTrees

Problem statement

Given the roots of two binary trees, p and q, decide whether they are identical. Two trees are identical when they have the same shape and every pair of nodes in matching positions holds the same value. Two empty trees are identical.

Trees are written in level order, with null for a missing child.

Examples

Example 1

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

Output: true

Example 2

Input: p = [4, 5], q = [4, null, 5]

Output: false

Explanation: Same values, but 5 is a left child in one tree and a right child in the other.

Hints

Approach

Walk both trees at the same time and compare node by node.

  1. If both nodes are empty, they match: return true.
  2. If exactly one is empty, or their values differ, return false.
  3. Otherwise return isSameTree(p.left, q.left) and isSameTree(p.right, q.right).

The and short-circuits, so the search stops at the first mismatch. No extra strings are built; the only extra memory is the recursion stack.

ComplexityTime O(min(n, m))Space O(h), where h is the height of the smaller tree
Python
from typing import Optional
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSameTree(self, p: Optional["TreeNode"], q: Optional["TreeNode"]) -> bool:
if p is None and q is None:
return True
if p is None or q is None or p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Follow-up questions

  • Decide whether one tree appears as a subtree anywhere inside another.
  • Instead of true or false, report the path to the first node where the two trees differ.

Frequently asked questions

Pre-order with null markers uniquely describes a tree. Plain in-order values without markers do not: many different shapes share the same in-order sequence. Stick with pre-order (or post-order) plus markers when you serialise for comparison.

Without one, the values 1, 23 and 12, 3 both become 123. A comma, or any character that cannot appear in a value, keeps the tokens apart.

Checking whether two config trees or two directory snapshots are identical is exactly this, and it is how drift detection starts. Real tools often hash each subtree, as Merkle trees do, so that equal subtrees can be skipped without walking them.