100. Same Tree

Same Tree (LeetCode 100) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Preorder Traversal subpattern.

• Blind 75 · #27 of 75 · Trees
• NeetCode 150 · #50 of 150 · Trees
• NeetCode 250 · #95 of 250 · Trees

How to solve Same Tree

Same Tree is a Preorder Traversal problem, part of Tree Traversal Patterns (DFS & BFS). Master preorder traversal for tree construction, inversion, and path problems. Visit root before children.

Work towards the solution in these steps:

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.

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

The Same Tree solution and editorial walks through the full approach with reference code.

Problem statement

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.

Example 1:

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

Example 2:

Input: p = [1,2], q = [1,null,2] Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2] Output: false

Constraints:

- The number of nodes in both trees is in the range [0, 100].

- -104 <= Node.val <= 104

Topics and companies

Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree.

Reported in interviews at Amazon, Google, Microsoft, Apple.

How to practise Same Tree on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(h) space.

Open Same Tree in the code editor, or read the Same Tree editorial for a worked solution with its approach and complexity analysis.

Where Same Tree sits in the DSA pattern sheet

• Tree Traversal Patterns (DFS & BFS) pattern guide
• Recursive Preorder Traversal subpattern
• The full DSA patterns sheet

Problems related to Same Tree

Other problems that use the same Recursive Preorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:

• Binary Tree Paths — Easy, same subpattern
• Binary Tree Preorder Traversal — Easy, same subpattern
• Construct Binary Tree from Preorder and Inorder Traversal — Medium, same subpattern
• Construct Quad Tree — Medium, same subpattern
• Count Good Nodes in Binary Tree — Medium, same subpattern
• Flatten Binary Tree to Linked List — Medium, same subpattern

Same Tree FAQ