100. Same Tree

At a Glance

Topic: trees
Pattern: Tree DFS
Difficulty: Easy
Companies: Amazon, Google, Meta, Bloomberg, Apple
Frequency: Very High
LeetCode: 100

Problem (one-liner)

Given the roots of two binary trees primary and secondary, return true if they are identical: same structure and same value at every corresponding node.

Recognition Cues

"Same tree" / "identical" trees
Structural equality plus value equality
Natural recursive definition: roots match and left subtrees match and right subtrees match

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — serializing both pre-order strings — O(n) time / O(n) space — works but more machinery than needed.
Better — iterative DFS with two stacks — O(n) time / O(n) space — same asymptotics, more code.
Optimal — O(n) time / O(h) stack — recursive DFS: compare values and recurse on left/right pairs.

Optimal Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isSameTree(primary *TreeNode, secondary *TreeNode) bool {
	if primary == nil && secondary == nil {
		return true
	}
	if primary == nil || secondary == nil {
		return false
	}
	if primary.Val != secondary.Val {
		return false
	}
	return isSameTree(primary.Left, secondary.Left) && isSameTree(primary.Right, secondary.Right)
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function isSameTree(primary, secondary) {
	if (primary === null && secondary === null) {
		return true;
	}
	if (primary === null || secondary === null) {
		return false;
	}
	if (primary.val !== secondary.val) {
		return false;
	}
	return (
		isSameTree(primary.left, secondary.left) &&
		isSameTree(primary.right, secondary.right)
	);
}