Easy — Binary Tree | Depth-First Search | Recursion

The Problem

Given the roots of two binary trees p and q, determine 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.

Approach

Use recursive depth-first traversal to compare both trees simultaneously. At each step, check if both nodes are null (base case), if one is null while the other isn’t, or if their values differ. Recursively verify that left and right subtrees are identical.

Time: O(min(m,n)) · Space: O(min(m,n))

Code

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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment