{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Same Tree – Solution & Complexity

Interview solutions
/
Same Tree

Solution Walkthrough

  1. Step 1: Recognize the Pattern

    The key pattern is: Parallel DFS compares corresponding nodes. Identify the state and invariant before coding.

  2. Step 2: Build the Algorithm

    Advance one state transition at a time. Mark or update state before exploring dependent work.

  3. Step 3: Check Edge Cases

    Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

  4. Step 4: Solution and Complexity

    Time: O(n). Space: O(h).

    Java/Go/Rust below are reference solutions for learning the pattern in those languages; only Python and JavaScript can be run and submitted for this problem, since the remote judge doesn't support the TreeNode structure yet.

    def is_same_tree(p: TreeNode, q: TreeNode) -> bool:
    if p is None or q is None:
        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)

FAQ

See also

Practice Same Tree online (run code in the browser)Balanced Binary Tree solution (easy)Binary Tree Inorder Traversal solution (easy)Binary Tree Postorder Traversal solution (easy)Binary Tree Preorder Traversal solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?