What is the optimal approach and complexity for Same Tree?

Recurse on both trees at once; any mismatch at a position returns false with optimal time complexity O(N) and space complexity O(H).

How do you identify the pattern for Same Tree?

Look for key signals in the prompt: "two trees" indicates Walk both trees at the same time, one pair of positions at a time.; "same shape and same values" indicates Every position must agree: both empty, or equal values and matching children.; "return true or false" indicates The answer is one AND over all the pairs, so the first false decides it..

Same Tree

Easy·LeetCode #100 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given the roots of two binary trees, p and q. Decide whether they are the same: they have the same shape, and every pair of nodes at the same position has the same value.

Return true if they are the same, otherwise false.

Input

Two roots, p and q. Either one may be empty.

Output

true if the two trees are the same, false otherwise.

Example 1

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

Output: true

The shapes match, and every position has the same value.

Example 2

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

Output: false

The values are in the same order, but 2 is a left child in p and a right child in q.

Example 3

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

Output: false

The shapes match, but the values of the two children are swapped.

Constraints

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

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“two trees”

→ Walk both trees at the same time, one pair of positions at a time.

“same shape and same values”

→ Every position must agree: both empty, or equal values and matching children.

“return true or false”

→ The answer is one AND over all the pairs, so the first false decides it.

Approach Complexity Ladder

Brute Force — serialize both trees and compare the stringsO(N)O(N)

Write each tree in preorder with # for empty children; the trees are the same when the texts are equal

Optimal — walk both trees togetherO(N)O(H)

Recurse on both trees at once; any mismatch at a position returns false

Brute Force Intuition

Write p as one long string: visit nodes in preorder, write each value, and write # for every empty child. Do the same for q. The # marks make the shape part of the text, so equal strings mean equal shapes and values.

Recognition rule for this sub-pattern:

Visit nodes in pre/in/post order or walk two trees together node by node.

Remember this · Tree DFS

Trigger

Paths, heights, diameters, validating structure, ancestors, anything "for every subtree".

Think

If my left and right children already gave me their answers, how do I build mine?

Key question

What does my recursive function return, and what do I pass down?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree DFS translate into production architectures and low-level memory mechanics.

LLD Architecture