C# LeetCode 100: Same Tree - (Easy)

#tutorial #programming #csharp

Problem

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

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

Code

public bool IsSameTree(TreeNode p, TreeNode q) {
        var stackP = new Stack<TreeNode>();
        var stackQ = new Stack<TreeNode>();
        stackP.Push(p);
        stackQ.Push(q);

        while (stackP.Count > 0 && stackQ.Count > 0)
        {
            var nodeP = stackP.Pop();
            var nodeQ = stackQ.Pop();

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

            stackP.Push(nodeP.right);
            stackP.Push(nodeP.left);
            stackQ.Push(nodeQ.right);
            stackQ.Push(nodeQ.left);
        }

        return stackP.Count == 0 && stackQ.Count == 0;
    }

Approach

Initialize two stacks
stackP for tree p
stackQ for tree q
Push the root nodes onto their respective stacks.
Iterative DFS (Depth First Search)

While both stacks have nodes:
- Pop the current nodes from each stack.
- Compare them according to three rules:

Comparison Rules

Both nodes are null → continue (identical so far).
Only one is null → return false (structure differs).
Values differ → return false (trees differ).

Push children onto the stacks

Push right first, then left. This ensures the left child is processed first (classic DFS pattern).
After the loop, if both stacks are empty → trees are identical → return true.

Otherwise → return false.

Key Mechanics

Two stacks simulate a parallel DFS traversal of both trees - click link to learn more about DFS.
Null checks first to quickly detect mismatched structures.
Right‑then‑left push order preserves the usual DFS sequence.
No recursion → avoids potential stack overflow on deep trees.

Example

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

Stack evolution (simplified):

Push roots → Compare (1 == 1)
Push children → Compare (2 == 2), then (3 == 3)
Both stacks empty → return true ✅

As always feel free to drop me a follow on Dev To or twitter/x

DEV Community