100. Same Tree

How to solve Same Tree (LeetCode 100): the approach in brief

The problem

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

Pattern

Same Tree is a Tree Traversal Patterns (DFS & BFS) problem, in the Recursive Preorder Traversal subpattern. The pattern covers preorder, inorder, level order traversal, LCA, and serialization

Master preorder traversal for tree construction, inversion, and path problems. Visit root before children.

Approach outline

1. Consider how you might compare two binary trees by traversing them simultaneously.
2. Think about using a recursive approach to explore both trees in the same order, such as preorder traversal.
3. At each step of the traversal, check if both nodes are null or if one is null and the other isn't.

Complexity

The reference solution runs in O(n) time and O(h) space.

Asked at

Same Tree has been reported in interviews at Amazon, Google, Microsoft, Apple.