Same Tree

Problem Statement

Given the roots of two binary trees p and q, write a function to check if they are the same.

Two binary trees are considered the same if they are structurally identical and the nodes have the same values.

What to notice first

• Structural equality means both left and right children must exist in both trees (or be absent in both).
• Value equality means every node at the same position must have the same integer value.
• An empty tree (null root) is considered the same as another empty tree.
• The test checks both structure AND values simultaneously — one mismatch anywhere fails the comparison.

Examples

p	q	Output	Explanation
[1,2,3]	[1,2,3]	true	Trees are identical in structure and values
[1,2]	[1,null,2]	false	Different structure (left vs. right child)
[1,2,1]	[1,1,2]	false	Same structure but different values at positions

Constraints

• The number of nodes in each tree is in the range [0, 100].
• -10^4 <= Node.val <= 10^4

Real-World Applications

Where this pattern appears

• Tree cloning validation — confirm that a copied tree structure is identical to the original before applying transformations.
• Configuration file comparison — compare two JSON/XML tree structures to detect configuration drift.
• DOM tree reconciliation — React and other frameworks compare virtual DOM trees to determine minimal updates.
• Expression tree equality — verify that two algebraic expressions represent the same mathematical formula.
• Backup verification — ensure a restored directory tree matches the original backup.

Complexity Comparison

Approach	Time	Space	Best When
DFS Recursive	O(min(m, n))	O(min(h1, h2))	Small trees; clean recursive code preferred
BFS Level-Order	O(min(m, n))	O(min(w1, w2))	Wide, shallow trees; iterative approach preferred

m and n = number of nodes; h = height; w = max width at any level

Which approach should you learn first?

• Learn DFS Recursive first — it is elegant, concise, and mirrors the recursive tree structure naturally.
• Use BFS as a variation if you want to practice iterative techniques or need explicit level-order thinking.

Elegant & Intuitive

DFS Recursive

O(min(m, n)) time · O(min(h1, h2)) space

Iterative Alternative

BFS Level-Order

O(min(m, n)) time · O(min(w1, w2)) space

Approach 1: DFS Recursive

★ Recommended

Compare nodes recursively by checking:

1. Are both nodes null? (equal)
2. Is exactly one null? (not equal)
3. Do values differ? (not equal)
4. Recursively check left and right subtrees

This mirrors the natural recursive structure of trees and reaches all nodes in minimal time.

⏱ Time O(min(m, n)) Each node visited at most once 💾 Space O(min(h1, h2)) Call stack depth = tree height

Step-by-step Example

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

    1               1
   / \             / \
  2   3           2   3

Step	Check	Result
Compare roots	p.val == q.val (1 == 1)	Continue
Left subtree	isSameTree(p.left=2, q.left=2)	true
Right subtree	isSameTree(p.right=3, q.right=3)	true
Result	Both children match	true

Animated walkthrough

How DFS recursion compares trees node-by-node

Use Next or Autoplay to see the algorithm recursively traverse and compare both trees simultaneously.

Back Autoplay Next Reset

Step 1 of 4

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function isSameTree(p, q):
    if p is null and q is null:
        return true
    if p is null or q is null:
        return false
    if p.val != q.val:
        return false
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

Solution Code

Python

same_tree_dfs.py

from typing import Optional


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


def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    """
    Check if two binary trees are the same using DFS (recursive).

    Time Complexity: O(min(m, n)) where m and n are the number of nodes in each tree
    Space Complexity: O(min(h1, h2)) where h1 and h2 are the heights of the trees (call stack)
    """
    # Both nodes are None (base case: equal)
    if p is None and q is None:
        return True

    # One is None, the other isn't (not equal)
    if p is None or q is None:
        return False

    # Values differ (not equal)
    if p.val != q.val:
        return False

    # Recursively check left and right subtrees
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)


# Test cases
if __name__ == "__main__":
    # Example 1: Same trees
    #     1           1
    #    / \         / \
    #   2   3       2   3
    p1 = TreeNode(1)
    p1.left = TreeNode(2)
    p1.right = TreeNode(3)

    q1 = TreeNode(1)
    q1.left = TreeNode(2)
    q1.right = TreeNode(3)

    print(isSameTree(p1, q1))  # Expected: True

    # Example 2: Different structure
    #     1           1
    #    /             \
    #   2               2
    p2 = TreeNode(1)
    p2.left = TreeNode(2)

    q2 = TreeNode(1)
    q2.right = TreeNode(2)

    print(isSameTree(p2, q2))  # Expected: False

    # Example 3: Different values
    #     1           1
    #    / \         / \
    #   2   1       1   2
    p3 = TreeNode(1)
    p3.left = TreeNode(2)
    p3.right = TreeNode(1)

    q3 = TreeNode(1)
    q3.left = TreeNode(1)
    q3.right = TreeNode(2)

    print(isSameTree(p3, q3))  # Expected: False

    # Example 4: Both empty
    p4 = None
    q4 = None
    print(isSameTree(p4, q4))  # Expected: True

C++

same_tree_dfs.cpp

#include <iostream>
using namespace std;

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) {}
};

bool isSameTree(TreeNode* p, TreeNode* q) {
    /*
    Check if two binary trees are the same using DFS (recursive).

    Time Complexity: O(min(m, n)) where m and n are the number of nodes
    Space Complexity: O(min(h1, h2)) where h1 and h2 are the heights (call stack)
    */

    // Both nodes are nullptr (base case: equal)
    if (p == nullptr && q == nullptr) {
        return true;
    }

    // One is nullptr, the other isn't (not equal)
    if (p == nullptr || q == nullptr) {
        return false;
    }

    // Values differ (not equal)
    if (p->val != q->val) {
        return false;
    }

    // Recursively check left and right subtrees
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

int main() {
    // Example 1: Same trees
    //     1           1
    //    / \         / \
    //   2   3       2   3
    TreeNode* p1 = new TreeNode(1);
    p1->left = new TreeNode(2);
    p1->right = new TreeNode(3);

    TreeNode* q1 = new TreeNode(1);
    q1->left = new TreeNode(2);
    q1->right = new TreeNode(3);

    cout << (isSameTree(p1, q1) ? "true" : "false") << endl;  // Expected: true

    // Example 2: Different structure
    //     1           1
    //    /             \
    //   2               2
    TreeNode* p2 = new TreeNode(1);
    p2->left = new TreeNode(2);

    TreeNode* q2 = new TreeNode(1);
    q2->right = new TreeNode(2);

    cout << (isSameTree(p2, q2) ? "true" : "false") << endl;  // Expected: false

    // Example 3: Different values
    //     1           1
    //    / \         / \
    //   2   1       1   2
    TreeNode* p3 = new TreeNode(1);
    p3->left = new TreeNode(2);
    p3->right = new TreeNode(1);

    TreeNode* q3 = new TreeNode(1);
    q3->left = new TreeNode(1);
    q3->right = new TreeNode(2);

    cout << (isSameTree(p3, q3) ? "true" : "false") << endl;  // Expected: false

    // Example 4: Both empty
    cout << (isSameTree(nullptr, nullptr) ? "true" : "false") << endl;  // Expected: true

    return 0;
}

Java

same_tree_dfs.java

import java.util.*;

public class same_tree_dfs {
    public static 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;
        }
    }

    /**
     * Check if two binary trees are the same using DFS (recursive).
     *
     * Time Complexity: O(min(m, n)) where m and n are the number of nodes
     * Space Complexity: O(min(h1, h2)) where h1 and h2 are the heights (call
     * stack)
     */
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        // Both nodes are null (base case: equal)
        if (p == null && q == null) {
            return true;
        }

        // One is null, the other isn't (not equal)
        if (p == null || q == null) {
            return false;
        }

        // Values differ (not equal)
        if (p.val != q.val) {
            return false;
        }

        // Recursively check left and right subtrees
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public static void main(String[] args) {
        // Example 1: Same trees
        //     1           1
        //    / \         / \
        //   2   3       2   3
        TreeNode p1 = new TreeNode(1);
        p1.left = new TreeNode(2);
        p1.right = new TreeNode(3);

        TreeNode q1 = new TreeNode(1);
        q1.left = new TreeNode(2);
        q1.right = new TreeNode(3);

        System.out.println(isSameTree(p1, q1)); // Expected: true

        // Example 2: Different structure
        //     1           1
        //    /             \
        //   2               2
        TreeNode p2 = new TreeNode(1);
        p2.left = new TreeNode(2);

        TreeNode q2 = new TreeNode(1);
        q2.right = new TreeNode(2);

        System.out.println(isSameTree(p2, q2)); // Expected: false

        // Example 3: Different values
        //     1           1
        //    / \         / \
        //   2   1       1   2
        TreeNode p3 = new TreeNode(1);
        p3.left = new TreeNode(2);
        p3.right = new TreeNode(1);

        TreeNode q3 = new TreeNode(1);
        q3.left = new TreeNode(1);
        q3.right = new TreeNode(2);

        System.out.println(isSameTree(p3, q3)); // Expected: false

        // Example 4: Both empty
        System.out.println(isSameTree(null, null)); // Expected: true
    }
}

JavaScript

same_tree_dfs.js

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

/**
 * Check if two binary trees are the same using DFS (recursive).
 *
 * Time Complexity: O(min(m, n)) where m and n are the number of nodes
 * Space Complexity: O(min(h1, h2)) where h1 and h2 are the heights (call stack)
 *
 * @param {TreeNode} p - First binary tree
 * @param {TreeNode} q - Second binary tree
 * @return {boolean} - True if the trees are the same, false otherwise
 */
function isSameTree(p, q) {
    // Both nodes are null (base case: equal)
    if (p === null && q === null) {
        return true;
    }

    // One is null, the other isn't (not equal)
    if (p === null || q === null) {
        return false;
    }

    // Values differ (not equal)
    if (p.val !== q.val) {
        return false;
    }

    // Recursively check left and right subtrees
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

// Test cases
if (require.main === module) {
    // Example 1: Same trees
    //     1           1
    //    / \         / \
    //   2   3       2   3
    const p1 = new TreeNode(1);
    p1.left = new TreeNode(2);
    p1.right = new TreeNode(3);

    const q1 = new TreeNode(1);
    q1.left = new TreeNode(2);
    q1.right = new TreeNode(3);

    console.log(isSameTree(p1, q1)); // Expected: true

    // Example 2: Different structure
    //     1           1
    //    /             \
    //   2               2
    const p2 = new TreeNode(1);
    p2.left = new TreeNode(2);

    const q2 = new TreeNode(1);
    q2.right = new TreeNode(2);

    console.log(isSameTree(p2, q2)); // Expected: false

    // Example 3: Different values
    //     1           1
    //    / \         / \
    //   2   1       1   2
    const p3 = new TreeNode(1);
    p3.left = new TreeNode(2);
    p3.right = new TreeNode(1);

    const q3 = new TreeNode(1);
    q3.left = new TreeNode(1);
    q3.right = new TreeNode(2);

    console.log(isSameTree(p3, q3)); // Expected: false

    // Example 4: Both empty
    console.log(isSameTree(null, null)); // Expected: true
}

module.exports = isSameTree;

Rust

same_tree_dfs.rs

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/// Check if two binary trees are the same using DFS (recursive).
///
/// Time Complexity: O(min(m, n)) where m and n are the number of nodes
/// Space Complexity: O(min(h1, h2)) where h1 and h2 are the heights (call stack)
pub fn is_same_tree(
    p: Option<Rc<RefCell<TreeNode>>>,
    q: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
    match (p, q) {
        // Both are None (base case: equal)
        (None, None) => true,
        // One is None, the other isn't (not equal)
        (None, Some(_)) | (Some(_), None) => false,
        // Both are Some, check value and recurse
        (Some(p_node), Some(q_node)) => {
            let p_ref = p_node.borrow();
            let q_ref = q_node.borrow();

            // Values must match
            if p_ref.val != q_ref.val {
                return false;
            }

            // Recursively check left and right subtrees
            is_same_tree(p_ref.left.clone(), q_ref.left.clone())
                && is_same_tree(p_ref.right.clone(), q_ref.right.clone())
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_same_trees() {
        // Example 1: Same trees
        //     1           1
        //    / \         / \
        //   2   3       2   3
        let p1 = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: Some(Rc::new(RefCell::new(TreeNode::new(2)))),
            right: Some(Rc::new(RefCell::new(TreeNode::new(3)))),
        })));

        let q1 = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: Some(Rc::new(RefCell::new(TreeNode::new(2)))),
            right: Some(Rc::new(RefCell::new(TreeNode::new(3)))),
        })));

        assert_eq!(is_same_tree(p1, q1), true);
    }

    #[test]
    fn test_different_structure() {
        // Example 2: Different structure
        //     1           1
        //    /             \
        //   2               2
        let p2 = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: Some(Rc::new(RefCell::new(TreeNode::new(2)))),
            right: None,
        })));

        let q2 = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: None,
            right: Some(Rc::new(RefCell::new(TreeNode::new(2)))),
        })));

        assert_eq!(is_same_tree(p2, q2), false);
    }

    #[test]
    fn test_different_values() {
        // Example 3: Different values
        //     1           1
        //    / \         / \
        //   2   1       1   2
        let p3 = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: Some(Rc::new(RefCell::new(TreeNode::new(2)))),
            right: Some(Rc::new(RefCell::new(TreeNode::new(1)))),
        })));

        let q3 = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: Some(Rc::new(RefCell::new(TreeNode::new(1)))),
            right: Some(Rc::new(RefCell::new(TreeNode::new(2)))),
        })));

        assert_eq!(is_same_tree(p3, q3), false);
    }

    #[test]
    fn test_both_empty() {
        // Example 4: Both empty
        assert_eq!(is_same_tree(None, None), true);
    }
}

Go

same_tree_dfs.go

package main

import "fmt"

/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

/**
 * Check if two binary trees are the same using DFS (recursive).
 *
 * Time Complexity: O(min(m, n)) where m and n are the number of nodes
 * Space Complexity: O(min(h1, h2)) where h1 and h2 are the heights (call stack)
 */
func IsSameTree(p *TreeNode, q *TreeNode) bool {
  // Both nodes are nil (base case: equal)
  if p == nil && q == nil {
    return true
  }

  // One is nil, the other isn't (not equal)
  if p == nil || q == nil {
    return false
  }

  // Values differ (not equal)
  if p.Val != q.Val {
    return false
  }

  // Recursively check left and right subtrees
  return IsSameTree(p.Left, q.Left) && IsSameTree(p.Right, q.Right)
}

func main() {
  // Example 1: Same trees
  //     1           1
  //    / \         / \
  //   2   3       2   3
  p1 := &TreeNode{
    Val: 1,
    Left: &TreeNode{
      Val: 2,
    },
    Right: &TreeNode{
      Val: 3,
    },
  }

  q1 := &TreeNode{
    Val: 1,
    Left: &TreeNode{
      Val: 2,
    },
    Right: &TreeNode{
      Val: 3,
    },
  }

  fmt.Println(IsSameTree(p1, q1)) // Expected: true

  // Example 2: Different structure
  //     1           1
  //    /             \
  //   2               2
  p2 := &TreeNode{
    Val: 1,
    Left: &TreeNode{
      Val: 2,
    },
  }

  q2 := &TreeNode{
    Val: 1,
    Right: &TreeNode{
      Val: 2,
    },
  }

  fmt.Println(IsSameTree(p2, q2)) // Expected: false

  // Example 3: Different values
  //     1           1
  //    / \         / \
  //   2   1       1   2
  p3 := &TreeNode{
    Val: 1,
    Left: &TreeNode{
      Val: 2,
    },
    Right: &TreeNode{
      Val: 1,
    },
  }

  q3 := &TreeNode{
    Val: 1,
    Left: &TreeNode{
      Val: 1,
    },
    Right: &TreeNode{
      Val: 2,
    },
  }

  fmt.Println(IsSameTree(p3, q3)) // Expected: false

  // Example 4: Both empty
  fmt.Println(IsSameTree(nil, nil)) // Expected: true
}

Approach 2: BFS Level-Order Traversal

alternative

Use a queue to store pairs of nodes from both trees. At each step, dequeue a pair, check if they match, and enqueue the children. This allows you to compare the trees level-by-level (breadth-first) instead of depth-first.

⏱ Time O(min(m, n)) Each node visited once 💾 Space O(min(w1, w2)) Queue holds at most max width nodes

Step-by-step Example

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

Queue State	Check	Enqueue	Status
[(1,1)]	1 == 1	(2,2), (3,3)	Match
[(2,2), (3,3)]	2 == 2	(null,null), (null,null)	Match
[(null,null), (3,3)]	Both null	—	Skip
[(3,3)]	3 == 3	(null,null), (null,null)	Match
[(null,null), (null,null)]	Both null	—	Skip
[]	All compared	—	true

Pseudocode

function isSameTree(p, q):
    queue = [(p, q)]
    while queue is not empty:
        node1, node2 = queue.dequeue()
        if node1 is null and node2 is null:
            continue
        if node1 is null or node2 is null or node1.val != node2.val:
            return false
        queue.enqueue((node1.left, node2.left))
        queue.enqueue((node1.right, node2.right))
    return true

Solution Code

Python

same_tree_bfs.py

from typing import Optional
from collections import deque


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


def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    """
    Check if two binary trees are the same using BFS (level-order traversal).

    Time Complexity: O(min(m, n)) where m and n are the number of nodes in each tree
    Space Complexity: O(min(w1, w2)) where w1 and w2 are the widths of the trees
    """
    # Use a queue to store pairs of nodes to compare
    queue = deque([(p, q)])

    while queue:
        node1, node2 = queue.popleft()

        # Both are None (equal)
        if node1 is None and node2 is None:
            continue

        # One is None or values differ (not equal)
        if node1 is None or node2 is None or node1.val != node2.val:
            return False

        # Add children to queue for comparison
        queue.append((node1.left, node2.left))
        queue.append((node1.right, node2.right))

    return True


# Test cases
if __name__ == "__main__":
    # Example 1: Same trees
    #     1           1
    #    / \         / \
    #   2   3       2   3
    p1 = TreeNode(1)
    p1.left = TreeNode(2)
    p1.right = TreeNode(3)

    q1 = TreeNode(1)
    q1.left = TreeNode(2)
    q1.right = TreeNode(3)

    print(isSameTree(p1, q1))  # Expected: True

    # Example 2: Different structure
    #     1           1
    #    /             \
    #   2               2
    p2 = TreeNode(1)
    p2.left = TreeNode(2)

    q2 = TreeNode(1)
    q2.right = TreeNode(2)

    print(isSameTree(p2, q2))  # Expected: False

    # Example 3: Different values
    #     1           1
    #    / \         / \
    #   2   1       1   2
    p3 = TreeNode(1)
    p3.left = TreeNode(2)
    p3.right = TreeNode(1)

    q3 = TreeNode(1)
    q3.left = TreeNode(1)
    q3.right = TreeNode(2)

    print(isSameTree(p3, q3))  # Expected: False

    # Example 4: Both empty
    p4 = None
    q4 = None
    print(isSameTree(p4, q4))  # Expected: True

C++

same_tree_bfs.cpp

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

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) {}
};

bool isSameTree(TreeNode* p, TreeNode* q) {
    /*
    Check if two binary trees are the same using BFS (level-order traversal).

    Time Complexity: O(min(m, n)) where m and n are the number of nodes
    Space Complexity: O(min(w1, w2)) where w1 and w2 are the widths
    */

    queue<pair<TreeNode*, TreeNode*>> que;
    que.push({p, q});

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

        // Both are nullptr (equal)
        if (node1 == nullptr && node2 == nullptr) {
            continue;
        }

        // One is nullptr or values differ (not equal)
        if (node1 == nullptr || node2 == nullptr || node1->val != node2->val) {
            return false;
        }

        // Add children to queue for comparison
        que.push({node1->left, node2->left});
        que.push({node1->right, node2->right});
    }

    return true;
}

int main() {
    // Example 1: Same trees
    //     1           1
    //    / \         / \
    //   2   3       2   3
    TreeNode* p1 = new TreeNode(1);
    p1->left = new TreeNode(2);
    p1->right = new TreeNode(3);

    TreeNode* q1 = new TreeNode(1);
    q1->left = new TreeNode(2);
    q1->right = new TreeNode(3);

    cout << (isSameTree(p1, q1) ? "true" : "false") << endl;  // Expected: true

    // Example 2: Different structure
    //     1           1
    //    /             \
    //   2               2
    TreeNode* p2 = new TreeNode(1);
    p2->left = new TreeNode(2);

    TreeNode* q2 = new TreeNode(1);
    q2->right = new TreeNode(2);

    cout << (isSameTree(p2, q2) ? "true" : "false") << endl;  // Expected: false

    // Example 3: Different values
    //     1           1
    //    / \         / \
    //   2   1       1   2
    TreeNode* p3 = new TreeNode(1);
    p3->left = new TreeNode(2);
    p3->right = new TreeNode(1);

    TreeNode* q3 = new TreeNode(1);
    q3->left = new TreeNode(1);
    q3->right = new TreeNode(2);

    cout << (isSameTree(p3, q3) ? "true" : "false") << endl;  // Expected: false

    // Example 4: Both empty
    cout << (isSameTree(nullptr, nullptr) ? "true" : "false") << endl;  // Expected: true

    return 0;
}

Java

same_tree_bfs.java

import java.util.*;

public class same_tree_bfs {
    public static 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;
        }
    }

    /**
     * Check if two binary trees are the same using BFS (level-order traversal).
     *
     * Time Complexity: O(min(m, n)) where m and n are the number of nodes
     * Space Complexity: O(min(w1, w2)) where w1 and w2 are the widths
     */
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode[]> queue = new LinkedList<>();
        queue.add(new TreeNode[]{p, q});

        while (!queue.isEmpty()) {
            TreeNode[] nodes = queue.poll();
            TreeNode node1 = nodes[0];
            TreeNode node2 = nodes[1];

            // Both are null (equal)
            if (node1 == null && node2 == null) {
                continue;
            }

            // One is null or values differ (not equal)
            if (node1 == null || node2 == null || node1.val != node2.val) {
                return false;
            }

            // Add children to queue for comparison
            queue.add(new TreeNode[]{node1.left, node2.left});
            queue.add(new TreeNode[]{node1.right, node2.right});
        }

        return true;
    }

    public static void main(String[] args) {
        // Example 1: Same trees
        //     1           1
        //    / \         / \
        //   2   3       2   3
        TreeNode p1 = new TreeNode(1);
        p1.left = new TreeNode(2);
        p1.right = new TreeNode(3);

        TreeNode q1 = new TreeNode(1);
        q1.left = new TreeNode(2);
        q1.right = new TreeNode(3);

        System.out.println(isSameTree(p1, q1)); // Expected: true

        // Example 2: Different structure
        //     1           1
        //    /             \
        //   2               2
        TreeNode p2 = new TreeNode(1);
        p2.left = new TreeNode(2);

        TreeNode q2 = new TreeNode(1);
        q2.right = new TreeNode(2);

        System.out.println(isSameTree(p2, q2)); // Expected: false

        // Example 3: Different values
        //     1           1
        //    / \         / \
        //   2   1       1   2
        TreeNode p3 = new TreeNode(1);
        p3.left = new TreeNode(2);
        p3.right = new TreeNode(1);

        TreeNode q3 = new TreeNode(1);
        q3.left = new TreeNode(1);
        q3.right = new TreeNode(2);

        System.out.println(isSameTree(p3, q3)); // Expected: false

        // Example 4: Both empty
        System.out.println(isSameTree(null, null)); // Expected: true
    }
}

JavaScript

same_tree_bfs.js

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

/**
 * Check if two binary trees are the same using BFS (level-order traversal).
 *
 * Time Complexity: O(min(m, n)) where m and n are the number of nodes
 * Space Complexity: O(min(w1, w2)) where w1 and w2 are the widths
 *
 * @param {TreeNode} p - First binary tree
 * @param {TreeNode} q - Second binary tree
 * @return {boolean} - True if the trees are the same, false otherwise
 */
function isSameTree(p, q) {
    const queue = [[p, q]];

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

        // Both are null (equal)
        if (node1 === null && node2 === null) {
            continue;
        }

        // One is null or values differ (not equal)
        if (node1 === null || node2 === null || node1.val !== node2.val) {
            return false;
        }

        // Add children to queue for comparison
        queue.push([node1.left, node2.left]);
        queue.push([node1.right, node2.right]);
    }

    return true;
}

// Test cases
if (require.main === module) {
    // Example 1: Same trees
    //     1           1
    //    / \         / \
    //   2   3       2   3
    const p1 = new TreeNode(1);
    p1.left = new TreeNode(2);
    p1.right = new TreeNode(3);

    const q1 = new TreeNode(1);
    q1.left = new TreeNode(2);
    q1.right = new TreeNode(3);

    console.log(isSameTree(p1, q1)); // Expected: true

    // Example 2: Different structure
    //     1           1
    //    /             \
    //   2               2
    const p2 = new TreeNode(1);
    p2.left = new TreeNode(2);

    const q2 = new TreeNode(1);
    q2.right = new TreeNode(2);

    console.log(isSameTree(p2, q2)); // Expected: false

    // Example 3: Different values
    //     1           1
    //    / \         / \
    //   2   1       1   2
    const p3 = new TreeNode(1);
    p3.left = new TreeNode(2);
    p3.right = new TreeNode(1);

    const q3 = new TreeNode(1);
    q3.left = new TreeNode(1);
    q3.right = new TreeNode(2);

    console.log(isSameTree(p3, q3)); // Expected: false

    // Example 4: Both empty
    console.log(isSameTree(null, null)); // Expected: true
}

module.exports = isSameTree;

Rust

same_tree_bfs.rs

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/// Check if two binary trees are the same using BFS (level-order traversal).
///
/// Time Complexity: O(min(m, n)) where m and n are the number of nodes
/// Space Complexity: O(min(w1, w2)) where w1 and w2 are the widths
pub fn is_same_tree(
    p: Option<Rc<RefCell<TreeNode>>>,
    q: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
    let mut queue = VecDeque::new();
    queue.push_back((p, q));

    while let Some((node1, node2)) = queue.pop_front() {
        match (node1, node2) {
            // Both are None (equal)
            (None, None) => continue,
            // One is None or values differ (not equal)
            (None, Some(_)) | (Some(_), None) => return false,
            // Both are Some, check value and add children to queue
            (Some(p_node), Some(q_node)) => {
                let p_ref = p_node.borrow();
                let q_ref = q_node.borrow();

                // Values must match
                if p_ref.val != q_ref.val {
                    return false;
                }

                // Add children to queue for comparison
                queue.push_back((p_ref.left.clone(), q_ref.left.clone()));
                queue.push_back((p_ref.right.clone(), q_ref.right.clone()));
            }
        }
    }

    true
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_same_trees() {
        // Example 1: Same trees
        //     1           1
        //    / \         / \
        //   2   3       2   3
        let p1 = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: Some(Rc::new(RefCell::new(TreeNode::new(2)))),
            right: Some(Rc::new(RefCell::new(TreeNode::new(3)))),
        })));

        let q1 = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: Some(Rc::new(RefCell::new(TreeNode::new(2)))),
            right: Some(Rc::new(RefCell::new(TreeNode::new(3)))),
        })));

        assert_eq!(is_same_tree(p1, q1), true);
    }

    #[test]
    fn test_different_structure() {
        // Example 2: Different structure
        //     1           1
        //    /             \
        //   2               2
        let p2 = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: Some(Rc::new(RefCell::new(TreeNode::new(2)))),
            right: None,
        })));

        let q2 = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: None,
            right: Some(Rc::new(RefCell::new(TreeNode::new(2)))),
        })));

        assert_eq!(is_same_tree(p2, q2), false);
    }

    #[test]
    fn test_different_values() {
        // Example 3: Different values
        //     1           1
        //    / \         / \
        //   2   1       1   2
        let p3 = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: Some(Rc::new(RefCell::new(TreeNode::new(2)))),
            right: Some(Rc::new(RefCell::new(TreeNode::new(1)))),
        })));

        let q3 = Some(Rc::new(RefCell::new(TreeNode {
            val: 1,
            left: Some(Rc::new(RefCell::new(TreeNode::new(1)))),
            right: Some(Rc::new(RefCell::new(TreeNode::new(2)))),
        })));

        assert_eq!(is_same_tree(p3, q3), false);
    }

    #[test]
    fn test_both_empty() {
        // Example 4: Both empty
        assert_eq!(is_same_tree(None, None), true);
    }
}

Go

same_tree_bfs.go

package main

import (
  "fmt"
)

/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

/**
 * Check if two binary trees are the same using BFS (level-order traversal).
 *
 * Time Complexity: O(min(m, n)) where m and n are the number of nodes
 * Space Complexity: O(min(w1, w2)) where w1 and w2 are the widths
 */
func IsSameTree(p *TreeNode, q *TreeNode) bool {
  // Use a queue to store pairs of nodes to compare
  queue := [][2]*TreeNode{{p, q}}

  for len(queue) > 0 {
    nodes := queue[0]
    queue = queue[1:]

    node1 := nodes[0]
    node2 := nodes[1]

    // Both are nil (equal)
    if node1 == nil && node2 == nil {
      continue
    }

    // One is nil or values differ (not equal)
    if node1 == nil || node2 == nil || node1.Val != node2.Val {
      return false
    }

    // Add children to queue for comparison
    queue = append(queue, [2]*TreeNode{node1.Left, node2.Left})
    queue = append(queue, [2]*TreeNode{node1.Right, node2.Right})
  }

  return true
}

func main() {
  // Example 1: Same trees
  //     1           1
  //    / \         / \
  //   2   3       2   3
  p1 := &TreeNode{
    Val: 1,
    Left: &TreeNode{
      Val: 2,
    },
    Right: &TreeNode{
      Val: 3,
    },
  }

  q1 := &TreeNode{
    Val: 1,
    Left: &TreeNode{
      Val: 2,
    },
    Right: &TreeNode{
      Val: 3,
    },
  }

  fmt.Println(IsSameTree(p1, q1)) // Expected: true

  // Example 2: Different structure
  //     1           1
  //    /             \
  //   2               2
  p2 := &TreeNode{
    Val: 1,
    Left: &TreeNode{
      Val: 2,
    },
  }

  q2 := &TreeNode{
    Val: 1,
    Right: &TreeNode{
      Val: 2,
    },
  }

  fmt.Println(IsSameTree(p2, q2)) // Expected: false

  // Example 3: Different values
  //     1           1
  //    / \         / \
  //   2   1       1   2
  p3 := &TreeNode{
    Val: 1,
    Left: &TreeNode{
      Val: 2,
    },
    Right: &TreeNode{
      Val: 1,
    },
  }

  q3 := &TreeNode{
    Val: 1,
    Left: &TreeNode{
      Val: 1,
    },
    Right: &TreeNode{
      Val: 2,
    },
  }

  fmt.Println(IsSameTree(p3, q3)) // Expected: false

  // Example 4: Both empty
  fmt.Println(IsSameTree(nil, nil)) // Expected: true
}

Watch for these pitfalls

• Null handling: Ensure both null nodes and non-null mismatches are checked before comparing values.
• Short-circuit evaluation: Both approaches stop and return false as soon as a mismatch is found — efficient pruning.
• Order doesn’t affect correctness: DFS and BFS visit nodes in different orders but both correctly determine equality.
• One structure, two algorithms: The same comparison logic applies; the difference is traversal order.

Related Problems

• Symmetric Tree Easy #101
• Maximum Depth of Binary Tree ↗ Easy #104
• Subtree of Another Tree ↗ Easy #572
• Invert Binary Tree ↗ Easy #226

Interview Tips

Key trade-offs to discuss

• DFS vs. BFS: DFS uses less queue memory for balanced trees but needs call stack space. BFS is iterative and predictable.
• Early termination: Both approaches stop on first mismatch — no need to finish traversing the entire trees if inequality is found early.
• Null nodes matter: In some problems, two null nodes are considered “the same.” Here they explicitly are — be clear on this.
• Follow-up: “How would you modify this to check if p is a subtree of q?” (Problem #572) — great discussion point.
• Tree validation: This pattern is foundational for tree comparison, cloning verification, and DOM reconciliation in frameworks.

← Previous
#98 Validate Binary Search Tree Next
#101 Symmetric Tree →