Leetcode - 100. Same Tree

The “Same Tree” problem is a classic interview question that tests your understanding of tree traversal. It asks:

Given two binary trees, check if they are structurally identical and node values are equal.

In this post, we'll walk through three elegant solutions:

1. Recursive (DFS)
2. Iterative with Queue (BFS)
3. Iterative with Stack (DFS)

By the end, you'll know when and why to choose each one.

---

📘 Problem Statement

You are given the roots of two binary trees p and q. Return true if the two trees are the same, otherwise return false.

Two binary trees are considered the same if:

• They are structurally identical
• Corresponding nodes have the same value

---

🧠 Approach 1: Recursive (Depth-First Search)

This is the cleanest and most natural solution.

✅ Logic:

• If both nodes are null, return true
• If one is null or values don’t match, return false
• Recurse on the left and right children

🧾 Code:

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

⏱️ Time Complexity:

O(n) – visit every node once

💾 Space Complexity:

O(h) – due to recursion stack

• Worst case (skewed tree): O(n)
• Best case (balanced): O(log n)

---

🔁 Approach 2: Iterative with Queue (Breadth-First Search)

This approach uses two queues and processes both trees level by level.

✅ Logic:

• Use two queues: one for each tree
• At each step, compare the nodes
• Enqueue their children in the same order

🧾 Code:

var isSameTree = function (p, q) {
    let queue1 = [p], queue2 = [q];

    while (queue1.length && queue2.length) {
        let node1 = queue1.shift();
        let node2 = queue2.shift();

        if (!node1 && !node2) continue;
        if (!node1 || !node2 || node1.val !== node2.val) return false;

        queue1.push(node1.left, node1.right);
        queue2.push(node2.left, node2.right);
    }

    return queue1.length === 0 && queue2.length === 0;
};

⏱️ Time Complexity:

O(n) – all nodes are visited once

💾 Space Complexity:

O(n) – due to the queue holding nodes

---

🧱 Approach 3: Iterative with Stack (Depth-First Search)

This simulates recursion using a manual stack.

✅ Logic:

• Use a stack to store pairs of nodes
• Pop the top pair and compare them
• Push their children (right first, then left)

🧾 Code:

var isSameTree = function (p, q) {
    const stack = [[p, q]];

    while (stack.length > 0) {
        const [node1, node2] = stack.pop();

        if (!node1 && !node2) continue;
        if (!node1 || !node2 || node1.val !== node2.val) return false;

        stack.push([node1.right, node2.right]);
        stack.push([node1.left, node2.left]);
    }

    return true;
};

⏱️ Time Complexity:

O(n) – visiting every node

💾 Space Complexity:

O(h) – similar to recursion

---

🧮 Comparison Table

Feature	Recursive DFS	Iterative BFS (Queue)	Iterative DFS (Stack)
Traversal Order	Depth-First	Breadth-First	Depth-First
Time Complexity	O(n)	O(n)	O(n)
Space Complexity	O(h)	O(n)	O(h)
Readability	✅ Cleanest	❌ Slightly verbose	⚖️ Middle ground
Risk of Stack Overflow	❌ Yes (deep tree)	✅ No	✅ No

---

✨ Final Thoughts

Each approach is valid, and the right one depends on the situation:

• Use recursion when you want elegant, readable code and the tree isn’t too deep.
• Use queue (BFS) if you want to process nodes level-by-level or avoid recursion limits.
• Use stack (DFS) if you want control like recursion without call stack overhead.