Skip to content

Volume ITechnology

4.14.5 — Same Tree ​

LeetCode 100 · Easy · ★ Blind 75

The problem ​

You are given the roots of two binary trees, p and q. Return true if the two trees are the same: the same shape, with the same value in every matching position. Otherwise return false.

  1        1
 / \      / \      →  true
2   3    2   3

  1        1
 /          \      →  false   (same values, different shape)
2            2

  1        1
 / \      / \      →  false   (same shape, different values)
2   1    1   2

Each tree has up to 100 nodes.

What the problem is really asking ​

Two trees are the same when:

  1. their roots hold the same value, and
  2. their left subtrees are the same, and
  3. their right subtrees are the same.

That definition already refers to itself on smaller trees, so it is a recursive check. The real question is: how do you walk two trees side by side, and what do you do when one of them runs out before the other?

The brute force ​

There is nothing slower worth writing. Any correct method must compare every pair of matching nodes, and this method compares each pair once.

The idea ​

Walk both trees at the same time, one pair of nodes per call. At each pair there are exactly three cases.

  1. Both nodes are missing. Two empty trees are the same. Return true.
  2. Exactly one node is missing. One tree has a node where the other has nothing, so the shapes differ. Return false.
  3. Both nodes exist. Their values must match, and both pairs of children must be the same.

The solution ​

python
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:                            # (1)
            return True
        if not p or not q:                             # (2)
            return False
        return (p.val == q.val                         # (3)
                and self.isSameTree(p.left, q.left)
                and self.isSameTree(p.right, q.right))
ts
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  if (!p && !q) return true;                           // (1)
  if (!p || !q) return false;                          // (2)
  return p.val === q.val                               // (3)
      && isSameTree(p.left, q.left)
      && isSameTree(p.right, q.right);
}

Line by line ​

(1) Both missing: the same. This is the base case that ends the recursion.

(2) Exactly one missing: different shapes. By the time we reach this line, line (1) has ruled out "both missing". So if either one is missing now, it must be exactly one.

The order of lines (1) and (2) matters. If line (2) came first, two missing nodes would match not p or not q and wrongly return false.

(3) Both present. Three things must all be true: equal values, same left subtrees, same right subtrees. and stops at the first False. So if the values differ, the subtrees are never even visited, and if the left subtrees differ, the right ones are skipped.

Trace ​

Take the third example: p is 1 with children 2 and 1, and q is 1 with children 1 and 2.

Call on (p, q)CaseResult
(1, 1)both present, values equal → check left pairwaits
(2, 1)both present, values 2 ≠ 1false
back at (1, 1)left pair was false, so and stopsfalse

The right pair is never visited.

Complexity, derived ​

Time. Each pair of matching nodes is compared at most once, and the walk stops at the first difference. So the time is O(n), where n is the size of the smaller tree.

Space. The recursion is as deep as the shorter tree is tall, so O(h).

Edge cases ​

  • Both trees empty. Line (1) returns true.
  • One tree empty. Line (2) returns false.
  • Same values, mirrored shape, like the second example. Line (2) catches it at the first missing child.

The serialising trap ​

A tempting shortcut is to write each tree out as a list of values, and compare the lists. Be careful. Listing the values in one order does not pin down the tree's shape.

  1          1
 /            \
2              2

Visiting "root, then left, then right" and skipping missing children gives [1, 2] for both. They are different trees.

The fix is to write a marker for every missing child too, like "1,2,#,#,#" and "1,#,2,#,#". Then the lists differ. That is exactly why 4.14.15 Serialize and Deserialize Binary Tree writes markers for empty children.

Variations you will meet ​

  • Symmetric Tree. Is a tree its own mirror? The same three-case check, but comparing left.left with right.right, and left.right with right.left.
  • Subtree of Another Tree. Use this function at every node of a bigger tree. That is the next page, 4.14.6.
  • Merge Two Binary Trees. The same side-by-side walk, building a new tree instead of comparing.

The general lesson: to compare or combine two trees, recurse on both at once, and handle the "missing node" cases first.

What the interviewer will push on ​

"Why does the both-missing check come first?" Otherwise two empty trees would fall into the one-missing case and return false.

"Can you compare by turning both trees into strings?" Only if you include markers for missing children. Without them, different trees can give the same string.

"Can you do it without recursion?" Yes. Use a queue of node pairs. Pop a pair, apply the three cases, and push the two child pairs.

One thing to volunteer: point out that and stops at the first mismatch, so the walk ends as soon as a difference is found.

Next: 4.14.6 Subtree of Another Tree. This function used as a helper, with a surprisingly fast alternative.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet