Same Tree

Same Tree looks easy. You just check if two trees are equal, right? But the interviewer wants to see if you can walk two trees at the same time and keep them in step. That careful side-by-side walk is the real test here.

🎯 The Problem

You get two binary trees. A binary tree is a structure where each node has a value and up to two children, a left child and a right child. Say if the two trees are exactly the same.

The rules:

• “Same” means the same shape and the same values in the same places.
• If one tree has a node where the other has nothing, they are not the same.
• If both have a node in the same spot but the values differ, they are not the same.
• Return true only when shape and values match everywhere.

Input:
   Tree p          Tree q
     1               1
    / \             / \
   2   3           2   3

Output: true

Explanation: Both trees have the same shape and the same values.

Here is a quick look at the two trees side by side. The shape and values must match at every spot.

🐢 Approach 1: Flatten Both Trees to Lists (Brute Force)

Turn each tree into a list, then compare the two lists.

The idea:

• Write down every value in a fixed order.
• Include the empty spots so the shape is recorded.
• Do this for both trees.

How it works:

• Compare the two lists item by item.
• Equal lists mean the trees match.

Why it is weak:

• You still walk both trees fully to build the lists.
• You pay extra memory for two whole lists.
• It adds a step without saving any work.

Here is the flatten-and-compare code:

def is_same_tree(p, q):
    def flat(node):
        if not node: return [None]
        return [node.val] + flat(node.left) + flat(node.right)
    return flat(p) == flat(q)

⚡ Approach 2: Compare As You Walk With Recursion (Best)

The idea in one line: walk both trees together and compare each pair of nodes as you go.

The idea:

• This is recursion. A function that calls itself on smaller pieces of the same problem.
• Either both nodes are empty or both exist.
• If both exist, their values must match.
• Then their left sides must match, and their right sides too.

How it works:

• Compare the current pair.
• Ask the same question about the left children.
• Ask it about the right children.
• Return true only when the value and both sides match.

Why it is fast:

• One pass. Each node is visited once.
• It stops early the moment any pair differs.

Here is the direct recursion code:

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

🔁 Approach 3: Compare As You Walk With a Queue (Alternative)

The idea in one line: same compare, but use a queue of node pairs instead of letting the function call itself.

The idea:

• A queue is a line where you add at the back and remove from the front.
• Hold pairs of nodes to check, not single nodes.

How it works:

• Pop a pair and compare it.
• Push the left pair and the right pair to the back.
• Keep going until the queue is empty or a pair differs.

Why use it:

• Same result as the recursion.
• It avoids deep recursion on a very tall tree.
• It is just longer to write than the recursive version.

The solution below shows how the recursion fans out across the tree.

Steps to Solve

1. If both nodes are empty, they match. Return true.
2. If only one node is empty, they differ. Return false.
3. If the two values are not equal, return false.
4. Recurse on the left children of both nodes.
5. Recurse on the right children of both nodes.
6. Return true only when the current values match and both sides match.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node *left;
    struct Node *right;
} Node;

// make a new tree node
Node *newNode(int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->val = val;
    n->left = NULL;
    n->right = NULL;
    return n;
}

// returns 1 if the two trees are the same, else 0
int isSameTree(Node *p, Node *q) {
    if (p == NULL && q == NULL) return 1;   // both empty: match
    if (p == NULL || q == NULL) return 0;   // one empty: differ
    if (p->val != q->val) return 0;         // values differ
    return isSameTree(p->left, q->left)     // check left side
        && isSameTree(p->right, q->right);  // check right side
}

int main(void) {
    Node *p = newNode(1);
    p->left = newNode(2);
    p->right = newNode(3);

    Node *q = newNode(1);
    q->left = newNode(2);
    q->right = newNode(3);

    printf("%s\n", isSameTree(p, q) ? "true" : "false");
    return 0;
}

true

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node *left;
    Node *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

bool isSameTree(Node *p, Node *q) {
    if (p == nullptr && q == nullptr) return true;  // both empty
    if (p == nullptr || q == nullptr) return false; // one empty
    if (p->val != q->val) return false;             // values differ
    return isSameTree(p->left, q->left)             // left side
        && isSameTree(p->right, q->right);          // right side
}

int main() {
    Node *p = new Node(1);
    p->left = new Node(2);
    p->right = new Node(3);

    Node *q = new Node(1);
    q->left = new Node(2);
    q->right = new Node(3);

    cout << (isSameTree(p, q) ? "true" : "false") << endl;
    return 0;
}

true

public class SameTree {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
    }

    public static boolean isSameTree(Node p, Node q) {
        if (p == null && q == null) return true;   // both empty
        if (p == null || q == null) return false;  // one empty
        if (p.val != q.val) return false;          // values differ
        return isSameTree(p.left, q.left)          // left side
            && isSameTree(p.right, q.right);       // right side
    }

    public static void main(String[] args) {
        Node p = new Node(1);
        p.left = new Node(2);
        p.right = new Node(3);

        Node q = new Node(1);
        q.left = new Node(2);
        q.right = new Node(3);

        System.out.println(isSameTree(p, q));
    }
}

true

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


def is_same_tree(p, q):
    if p is None and q is None:      # both empty: match
        return True
    if p is None or q is None:       # one empty: differ
        return False
    if p.val != q.val:               # values differ
        return False
    return is_same_tree(p.left, q.left) and \
        is_same_tree(p.right, q.right)  # both sides must match


p = Node(1)
p.left = Node(2)
p.right = Node(3)

q = Node(1)
q.left = Node(2)
q.right = Node(3)

print(is_same_tree(p, q))

True

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function isSameTree(p, q) {
  if (p === null && q === null) return true;  // both empty
  if (p === null || q === null) return false; // one empty
  if (p.val !== q.val) return false;          // values differ
  return isSameTree(p.left, q.left)           // left side
    && isSameTree(p.right, q.right);          // right side
}

const p = new Node(1);
p.left = new Node(2);
p.right = new Node(3);

const q = new Node(1);
q.left = new Node(2);
q.right = new Node(3);

console.log(isSameTree(p, q));

true

Let us walk through the Python version line by line so you see why each line is there.

The function starts with if p is None and q is None: return True. This is the happy base case. A base case is the simplest input where recursion stops without calling itself again. If we walked off the bottom of both trees at the same spot, they match here.

Next is if p is None or q is None: return False. We already know they are not both empty. So if one is empty now, only one is. That means the shapes differ. We stop with false.

Then if p.val != q.val: return False. Both nodes exist here. If their values are not equal, the trees differ at this spot. We stop.

Finally return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right). The current pair matched. So now we ask the same question about the left children, then about the right children. The and means both sides must come back true for this spot to be true.

⏱️ Time and Space Complexity

Both the recursive and iterative ways visit every node once. So the time is O(n), where n is the number of nodes. The recursion uses memory for the call stack, which goes as deep as the tree is tall. So the space is O(h), where h is the height of the tree. For a balanced tree that is small. For a long thin tree it can reach O(n).

🧩 Key Takeaways

• ✅ Walk both trees together, comparing one pair of nodes at a time.
• ✅ Two nodes match when both are empty, or both exist with equal values and matching sides.
• ✅ Check the empty cases before you read any value, or the code crashes.
• ✅ The recursion fans out to the left side and the right side at every step.
• ✅ Time is O(n) and the recursion depth is O(h), the height of the tree.

🚀 What’s Next?

• Subtree of Another Tree
• Symmetric Tree