100. Same Tree - Explanation

Description

Given the roots of two binary trees p and q, return true if the trees are equivalent, otherwise return false.

Two binary trees are considered equivalent if they share the exact same structure and the nodes have the same values.

Example 1:

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

Output: true

Example 2:

Input: p = [4,7], q = [4,null,7]

Output: false

Example 3:

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

Output: false

Constraints:

0 <= The number of nodes in both trees <= 100.
-100 <= Node.val <= 100

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the tree.

Hint 1

Can you think of an algorithm that is used to traverse the tree? Maybe in terms of recursion.

Hint 2

We can use the Depth First Search (DFS) algorithm to traverse the tree. Can you think of a way to simultaneously traverse both the trees?

Hint 3

We traverse both trees starting from their root nodes. At each step in the recursion, we check if the current nodes in both trees are either null or have the same value. If one node is null while the other is not, or if their values differ, we return false. If the values match, we recursively check their left and right subtrees. If any recursive call returns false, the result for the current recursive call is false.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary tree structure - Understanding nodes with left/right children and null references
Tree traversal (DFS) - Recursively visiting nodes in a binary tree
Recursion - Using recursive function calls to process tree structures
Base case handling - Properly handling null nodes as termination conditions

1. Depth First Search

Intuition

Two binary trees are the same if:

Their structure is identical.
Their corresponding nodes have the same values.

So at every position:

If both nodes are null → they match.
If one is null but the other isn't → mismatch.
If both exist but values differ → mismatch.
Otherwise, compare their left subtrees and right subtrees recursively.

This is a direct structural + value-based DFS comparison.

Algorithm

If both p and q are null, return true.
If only one is null, return false.
If their values differ, return false.
Recursively compare:
- p.left with q.left
- p.right with q.right
Return true only if both subtree comparisons are true.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if p and q and p.val == q.val:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return False

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p != null && q != null && p.val == q.val) {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        } else {
            return false;
        }
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) {
            return true;
        }
        if (p && q && p->val == q->val) {
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        } else {
            return false;
        }
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    /**
     * @param {TreeNode} p
     * @param {TreeNode} q
     * @return {boolean}
     */
    isSameTree(p, q) {
        if (!p && !q) {
            return true;
        }
        if (p && q && p.val === q.val) {
            return (
                this.isSameTree(p.left, q.left) &&
                this.isSameTree(p.right, q.right)
            );
        } else {
            return false;
        }
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p != null && q != null && p.val == q.val) {
            return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
        } else {
            return false;
        }
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p != nil && q != nil && p.Val == q.Val {
        return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
    }
    return false
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
        if (p == null && q == null) {
            return true
        }
        if (p != null && q != null && p.`val` == q.`val`) {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
        }
        return false
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        if p == nil && q == nil {
            return true
        }
        if let p = p, let q = q, p.val == q.val {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
        } else {
            return false
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ $O (n)$
- Best Case (balanced tree): $O(log(n))$
- Worst Case (degenerate tree): $O(n)$

Where $n$ is the number of nodes in the tree and $h$ is the height of the tree.

2. Iterative DFS

Intuition

Instead of using recursion, we can use an explicit stack to compare the two trees.
Each stack entry contains a pair of nodes—one from each tree—that should match.

For every pair:

If both are null, they match → continue.
If only one is null, or their values differ → trees are not the same.
If they match, push their children in the same order:
- Left child pair
- Right child pair

If we finish processing all pairs with no mismatch, the trees are identical.

Algorithm

Initialize a stack with the pair (p, q).
While the stack is not empty:
- Pop a pair (node1, node2).
- If both are null, continue.
- If exactly one is null, return false.
- If node1.val != node2.val, return false.
- Push:
  - (node1.left, node2.left)
  - (node1.right, node2.right)
After the loop finishes, return true (all nodes matched).

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        stack = [(p, q)]

        while stack:
            node1, node2 = stack.pop()

            if not node1 and not node2:
                continue
            if not node1 or not node2 or node1.val != node2.val:
                return False

            stack.append((node1.right, node2.right))
            stack.append((node1.left, node2.left))

        return True

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Stack<TreeNode[]> stack = new Stack<>();
        stack.push(new TreeNode[]{p, q});

        while (!stack.isEmpty()) {
            TreeNode[] nodes = stack.pop();
            TreeNode node1 = nodes[0], node2 = nodes[1];

            if (node1 == null && node2 == null) continue;
            if (node1 == null || node2 == null || node1.val != node2.val) {
                return false;
            }
            stack.push(new TreeNode[]{node1.right, node2.right});
            stack.push(new TreeNode[]{node1.left, node2.left});
        }

        return true;
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        stack<pair<TreeNode*, TreeNode*>> stk;
        stk.push({p, q});

        while (!stk.empty()) {
            auto [node1, node2] = stk.top();
            stk.pop();

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

            stk.push({node1->right, node2->right});
            stk.push({node1->left, node2->left});
        }

        return true;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    /**
     * @param {TreeNode} p
     * @param {TreeNode} q
     * @return {boolean}
     */
    isSameTree(p, q) {
        const stack = [[p, q]];

        while (stack.length) {
            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;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        var stack = new Stack<(TreeNode, TreeNode)>();
        stack.Push((p, q));

        while (stack.Count > 0) {
            var (node1, node2) = stack.Pop();

            if (node1 == null && node2 == null) continue;
            if (node1 == null || node2 == null || node1.val != node2.val) {
                return false;
            }
            stack.Push((node1.right, node2.right));
            stack.Push((node1.left, node2.left));
        }

        return true;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    type Pair struct {
        first, second *TreeNode
    }

    stack := []Pair{{p, q}}

    for len(stack) > 0 {
        lastIdx := len(stack) - 1
        node1, node2 := stack[lastIdx].first, stack[lastIdx].second
        stack = stack[:lastIdx]

        if node1 == nil && node2 == nil {
            continue
        }
        if node1 == nil || node2 == nil || node1.Val != node2.Val {
            return false
        }

        stack = append(stack, Pair{node1.Right, node2.Right})
        stack = append(stack, Pair{node1.Left, node2.Left})
    }

    return true
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
        val stack = ArrayDeque<Pair<TreeNode?, TreeNode?>>()
        stack.addLast(Pair(p, q))

        while (stack.isNotEmpty()) {
            val (node1, node2) = stack.removeLast()

            if (node1 == null && node2 == null) continue
            if (node1 == null || node2 == null || node1.`val` != node2.`val`) {
                return false
            }
            stack.addLast(Pair(node1.right, node2.right))
            stack.addLast(Pair(node1.left, node2.left))
        }

        return true
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        var stack: [(TreeNode?, TreeNode?)] = [(p, q)]

        while !stack.isEmpty {
            let (node1, node2) = stack.removeLast()

            if node1 == nil && node2 == nil {
                continue
            }
            if node1 == nil || node2 == nil || node1!.val != node2!.val {
                return false
            }

            stack.append((node1!.right, node2!.right))
            stack.append((node1!.left, node2!.left))
        }

        return true
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Breadth First Search

Intuition

BFS (level-order traversal) lets us compare the two trees level by level.
We maintain two queues—one for each tree. At every step, we remove a pair of nodes
that should match:

If both nodes are null, they match → continue.
If only one is null, or their values differ → trees are not the same.
If they match, we push their children into their respective queues
in the same order: left child first, then right child.

Algorithm

Initialize two queues:
- q1 containing the root of the first tree.
- q2 containing the root of the second tree.
While both queues are non-empty:
- Pop one node from each queue: nodeP, nodeQ.
- If both are null, continue.
- If only one is null, return false.
- If their values differ, return false.
- Enqueue their children:
  - Left children of both trees.
  - Right children of both trees.
After BFS completes with no mismatch, return true.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        q1 = deque([p])
        q2 = deque([q])

        while q1 and q2:
            for _ in range(len(q1)):
                nodeP = q1.popleft()
                nodeQ = q2.popleft()

                if nodeP is None and nodeQ is None:
                    continue
                if nodeP is None or nodeQ is None or nodeP.val != nodeQ.val:
                    return False

                q1.append(nodeP.left)
                q1.append(nodeP.right)
                q2.append(nodeQ.left)
                q2.append(nodeQ.right)

        return True

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        q1.add(p);
        q2.add(q);

        while (!q1.isEmpty() && !q2.isEmpty()) {
            for (int i = q1.size(); i > 0; i--) {
                TreeNode nodeP = q1.poll();
                TreeNode nodeQ = q2.poll();

                if (nodeP == null && nodeQ == null) continue;
                if (nodeP == null || nodeQ == null || nodeP.val != nodeQ.val)
                    return false;

                q1.add(nodeP.left);
                q1.add(nodeP.right);
                q2.add(nodeQ.left);
                q2.add(nodeQ.right);
            }
        }

        return true;
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode*> q1;
        queue<TreeNode*> q2;
        q1.push(p);
        q2.push(q);

        while (!q1.empty() && !q2.empty()) {
            for (int i = q1.size(); i > 0; i--) {
                TreeNode* nodeP = q1.front(); q1.pop();
                TreeNode* nodeQ = q2.front(); q2.pop();

                if (!nodeP && !nodeQ) continue;
                if (!nodeP || !nodeQ || nodeP->val != nodeQ->val)
                    return false;

                q1.push(nodeP->left);
                q1.push(nodeP->right);
                q2.push(nodeQ->left);
                q2.push(nodeQ->right);
            }
        }

        return true;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    /**
     * @param {TreeNode} p
     * @param {TreeNode} q
     * @return {boolean}
     */
    isSameTree(p, q) {
        const q1 = new Queue();
        const q2 = new Queue();
        q1.push(p);
        q2.push(q);

        while (!q1.isEmpty() && !q2.isEmpty()) {
            for (let i = q1.size(); i > 0; i--) {
                let nodeP = q1.pop();
                let nodeQ = q2.pop();

                if (nodeP === null && nodeQ === null) continue;
                if (
                    nodeP === null ||
                    nodeQ === null ||
                    nodeP.val !== nodeQ.val
                ) {
                    return false;
                }

                q1.push(nodeP.left);
                q1.push(nodeP.right);
                q2.push(nodeQ.left);
                q2.push(nodeQ.right);
            }
        }

        return true;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        var q1 = new Queue<TreeNode>(new[] { p });
        var q2 = new Queue<TreeNode>(new[] { q });

        while (q1.Count > 0 && q2.Count > 0) {
            for (int i = q1.Count; i > 0; i--) {
                var nodeP = q1.Dequeue();
                var nodeQ = q2.Dequeue();

                if (nodeP == null && nodeQ == null) continue;
                if (nodeP == null || nodeQ == null || nodeP.val != nodeQ.val) {
                    return false;
                }

                q1.Enqueue(nodeP.left);
                q1.Enqueue(nodeP.right);
                q2.Enqueue(nodeQ.left);
                q2.Enqueue(nodeQ.right);
            }
        }

        return true;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    queue1 := []*TreeNode{p}
    queue2 := []*TreeNode{q}

    for len(queue1) > 0 && len(queue2) > 0 {
        for i := len(queue1); i > 0; i-- {
            nodeP := queue1[0]
            nodeQ := queue2[0]
            queue1 = queue1[1:]
            queue2 = queue2[1:]

            if nodeP == nil && nodeQ == nil {
                continue
            }
            if nodeP == nil || nodeQ == nil || nodeP.Val != nodeQ.Val {
                return false
            }

            queue1 = append(queue1, nodeP.Left, nodeP.Right)
            queue2 = append(queue2, nodeQ.Left, nodeQ.Right)
        }
    }

    return len(queue1) == 0 && len(queue2) == 0
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
        val q1 = ArrayDeque<TreeNode?>()
        val q2 = ArrayDeque<TreeNode?>()

        q1.add(p)
        q2.add(q)

        while (q1.isNotEmpty() && q2.isNotEmpty()) {
            for (i in q1.size downTo 1) {
                val nodeP = q1.removeFirst()
                val nodeQ = q2.removeFirst()

                if (nodeP == null && nodeQ == null) {
                    continue
                }
                if (nodeP == null || nodeQ == null || nodeP.`val` != nodeQ.`val`) {
                    return false
                }

                q1.add(nodeP.left)
                q1.add(nodeP.right)
                q2.add(nodeQ.left)
                q2.add(nodeQ.right)
            }
        }

        return true
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        var q1 = Deque<TreeNode?>()
        var q2 = Deque<TreeNode?>()
        q1.append(p)
        q2.append(q)

        while !q1.isEmpty && !q2.isEmpty {
            let nodeP = q1.removeFirst()
            let nodeQ = q2.removeFirst()

            if nodeP == nil && nodeQ == nil {
                continue
            }
            if nodeP == nil || nodeQ == nil || nodeP!.val != nodeQ!.val {
                return false
            }

            q1.append(nodeP!.left)
            q1.append(nodeP!.right)
            q2.append(nodeQ!.left)
            q2.append(nodeQ!.right)
        }

        return true
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Incorrect Null Check Order

A common mistake is checking node values before verifying both nodes exist. If one node is null and you access its value, you get a null pointer exception. Always check if both nodes are null first, then if exactly one is null, before comparing values.

Comparing Only Values Without Structure

Some solutions compare just the values using traversals like inorder or preorder, ignoring tree structure. Two trees can have identical traversal sequences but different structures. You must verify both the values and the structural positions match at every node.