100. Same Tree (Easy)

Problem

Given the roots of two binary trees p and q, return true if they are the same tree. Two binary trees are considered the same if they are structurally identical and the nodes have the same values.

Example

• p = [1,2,3], q = [1,2,3] → true
• p = [1,2], q = [1,null,2] → false

LeetCode 100 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Recursive DFS (canonical)

Compare roots, then recurse into matching children.

Python

def is_same_tree(p, q):
    if not p and not q:      # L1: both null = same
        return True
    if not p or not q:       # L2: one null = different structure
        return False
    return (p.val == q.val                          # L3: O(1) value compare
            and is_same_tree(p.left, q.left)        # L4: recurse left
            and is_same_tree(p.right, q.right))     # L5: recurse right

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    if (!p && !q) return true;      // L1: both null = same
    if (!p || !q) return false;     // L2: one null = different structure
    return (p.val === q.val                         // L3: O(1) value compare
         && isSameTree(p.left, q.left)              // L4: recurse left
         && isSameTree(p.right, q.right));          // L5: recurse right
}

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true                  // L1: both null = same
    }
    if p == nil || q == nil {
        return false                 // L2: one null = different structure
    }
    return p.Val == q.Val &&         // L3: O(1) value compare
        isSameTree(p.Left, q.Left) && // L4: recurse left
        isSameTree(p.Right, q.Right)  // L5: recurse right
}

Swift

final class Solution {
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        guard let p, let q else { return p == nil && q == nil }
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    }
}

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L1 (null check)	$O(1)$	up to n	$O(n)$
L2 (structure check)	$O(1)$	up to n	$O(n)$
L3 (value compare)	$O(1)$	up to n	$O(n)$
L4/L5 (recurse children)	$O(1)$ dispatch	n	$O(n)$ ← dominates (all lines tie)

Each node pair is visited at most once. The recursion short-circuits as soon as a mismatch is found, so best case is $O(1)$ (root values differ), worst case $O(n)$ (identical trees).

Complexity

• Time: $O(n)$, driven by L4/L5 visiting every node pair once.
• Space: $O(h)$ recursion depth.

Approach 2: Iterative BFS over paired nodes

Queue of (p_node, q_node) pairs; compare, then enqueue corresponding children.

Python

from collections import deque

def is_same_tree(p, q):
    q_pairs = deque([(p, q)])          # L1: O(1) init
    while q_pairs:
        a, b = q_pairs.popleft()       # L2: O(1) dequeue
        if not a and not b:
            continue                   # L3: both null, OK
        if not a or not b or a.val != b.val:
            return False               # L4: O(1) check
        q_pairs.append((a.left, b.left))    # L5: O(1) enqueue
        q_pairs.append((a.right, b.right))  # L6: O(1) enqueue
    return True

TypeScript

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    const queue: [TreeNode | null, TreeNode | null][] = [[p, q]];  // L1: O(1) init
    while (queue.length) {
        const [a, b] = queue.shift()!;                              // L2: O(1) dequeue
        if (!a && !b) continue;                                     // L3: both null, OK
        if (!a || !b || a.val !== b.val) return false;              // L4: O(1) check
        queue.push([a.left, b.left]);                               // L5: O(1) enqueue
        queue.push([a.right, b.right]);                             // L6: O(1) enqueue
    }
    return true;
}

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type pair struct{ a, b *TreeNode }

func isSameTree(p *TreeNode, q *TreeNode) bool {
    queue := []pair{{p, q}}                        // L1: O(1) init
    for len(queue) > 0 {
        pr := queue[0]
        queue = queue[1:]                          // L2: O(1) dequeue
        a, b := pr.a, pr.b
        if a == nil && b == nil {
            continue                               // L3: both null, OK
        }
        if a == nil || b == nil || a.Val != b.Val {
            return false                           // L4: O(1) check
        }
        queue = append(queue, pair{a.Left, b.Left})   // L5: O(1) enqueue
        queue = append(queue, pair{a.Right, b.Right}) // L6: O(1) enqueue
    }
    return true
}

Swift

final class Solution {
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        var queue: [(TreeNode?, TreeNode?)] = [(p, q)]
        var index = 0
        while index < queue.count {
            let pair = queue[index]
            index += 1
            if pair.0 == nil || pair.1 == nil { if pair.0 != nil || pair.1 != nil { return false }; continue }
            guard let left = pair.0, let right = pair.1, left.val == right.val else { return false }
            queue.append((left.left, right.left))
            queue.append((left.right, right.right))
        }
        return true
    }
}

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L2 (dequeue)	$O(1)$	n	$O(n)$
L4 (check)	$O(1)$	n	$O(n)$
L5/L6 (enqueue children)	$O(1)$	n	$O(n)$ ← dominates (all lines tie)

Same $O(n)$ total; queue holds at most $O(w)$ pairs where w is the max tree width.

Complexity

• Time: $O(n)$.
• Space: $O(w)$, width of the trees.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Serialize and compare

Serialize both trees with null markers and compare the strings.

Python

def is_same_tree(p, q):
    def serialize(node):               # L1: preorder DFS
        if not node:
            return "#"
        return f"{node.val},{serialize(node.left)},{serialize(node.right)}"  # L2: O(n) string build
    return serialize(p) == serialize(q)  # L3: O(n) string compare

Swift

final class Solution {
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool { serialize(p) == serialize(q) }
    private func serialize(_ node: TreeNode?) -> String {
        guard let node else { return "#" }
        return "\(node.val),\(serialize(node.left)),\(serialize(node.right))"
    }
}

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L1 (DFS dispatch)	$O(1)$	n	$O(n)$
L2 (string concat)	$O(n)$ per node due to f-string	n	$O(n²)$ ← dominates
L3 (string compare)	$O(n)$	1	$O(n)$

The f-string approach creates a new string at each node by concatenating partial results, making it $O(n²)$ in practice. Using parts.append + "".join at the end would make it $O(n)$.

Complexity

• Time: $O(n)$ with join; $O(n²)$ as written due to string concatenation.
• Space: $O(n)$ for the serialized strings.

Correct but wasteful; included because it shows the structural equality of the problem and serialization.

Summary

Approach	Time	Space
Recursive DFS	$O(n)$	$O(h)$
Iterative BFS on pairs	$O(n)$	$O(w)$
Serialize + compare	$O(n)$	$O(n)$

The recursive one-liner is the canonical answer. The paired-BFS variant is the template for iterative structural comparisons.

Test cases

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = [root]
    i = 1
    while q and i < len(vals):
        node = q.pop(0)
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

def is_same_tree(p, q):
    if not p and not q:
        return True
    if not p or not q:
        return False
    return (p.val == q.val
            and is_same_tree(p.left, q.left)
            and is_same_tree(p.right, q.right))

def _run_tests():
    # identical trees
    assert is_same_tree(build_tree([1, 2, 3]), build_tree([1, 2, 3])) == True
    # different structure
    assert is_same_tree(build_tree([1, 2]), build_tree([1, None, 2])) == False
    # both empty
    assert is_same_tree(None, None) == True
    # one empty
    assert is_same_tree(build_tree([1]), None) == False
    # single node same
    assert is_same_tree(build_tree([1]), build_tree([1])) == True
    # different values
    assert is_same_tree(build_tree([1, 2, 3]), build_tree([1, 2, 4])) == False
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function buildTree(vals: (number | null)[]): TreeNode | null {
    if (!vals.length) return null;
    const root = new TreeNode(vals[0] as number);
    const q: TreeNode[] = [root];
    let i = 1;
    while (q.length && i < vals.length) {
        const node = q.shift()!;
        if (i < vals.length && vals[i] !== null) { node.left = new TreeNode(vals[i] as number); q.push(node.left); }
        i++;
        if (i < vals.length && vals[i] !== null) { node.right = new TreeNode(vals[i] as number); q.push(node.right); }
        i++;
    }
    return root;
}

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    if (!p && !q) return true;
    if (!p || !q) return false;
    return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

console.assert(isSameTree(buildTree([1, 2, 3]), buildTree([1, 2, 3])) === true);
console.assert(isSameTree(buildTree([1, 2]), buildTree([1, null, 2])) === false);
console.assert(isSameTree(null, null) === true);
console.assert(isSameTree(buildTree([1]), null) === false);
console.assert(isSameTree(buildTree([1]), buildTree([1])) === true);
console.assert(isSameTree(buildTree([1, 2, 3]), buildTree([1, 2, 4])) === false);
console.log("all tests pass");

Related data structures

• Binary Trees & BSTs, paired structural recursion

Related concepts

• DFS, depth-first traversal tactics for exploring one branch fully before backtracking to alternatives.
• Recursion, self-similar problem-solving tactics for trees, divide-and-conquer, and search branches.