Is Same Tree easy or hard?

Same Tree is categorized as an Easy problem. It focuses on basic binary tree traversal and recursion patterns, making it a common introductory question for tree-based algorithms.

How to solve Same Tree in O(n)?

Traverse both trees simultaneously using DFS. At each step compare the current nodes: if both are null continue, if only one is null or their values differ return false. Recursively or iteratively compare left children and right children. Each node is processed once, resulting in O(n) time.

What is the best approach for Same Tree?

The recursive depth-first comparison is the most common and clean solution. You compare the current nodes of both trees, then recursively compare their left and right children. Each node is visited once, giving O(n) time and O(h) recursion stack space where h is the tree height.

Is Same Tree asked at Google/Amazon/Meta?

Same Tree is a common binary tree interview problem and appears frequently across companies such as Amazon, Meta, and Google in different variations. It tests understanding of tree traversal, recursion, and structural comparison.

What data structure is used in Same Tree?

The problem operates on a binary tree data structure. Solutions typically use Depth-First Search traversal, either through recursion or an explicit stack to compare nodes from both trees.

What is the time complexity of Same Tree?

The time complexity is O(n) because each node in the trees is visited once during comparison. In the worst case both trees contain n nodes and every corresponding pair must be checked.

Same Tree Python or Java solution approach?

Both Python and Java implementations typically use a recursive DFS function that compares node values and recursively checks left and right children. The logic is identical across languages and runs in O(n) time with O(h) stack space.

Description Solution Video 7:52

100. Same Tree

Easy68.0% acceptance9 companies

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].
-10⁴ <= Node.val <= 10⁴

Asked at 9 companies

Google Amazon Meta Bloomberg SAP Microsoft Apple LinkedIn

TCS

Topics

7:52

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2,3]
[1,2,3]

Input

[1,2]
[1,null,2]

Input

[1,2,1]
[1,1,2]

Your code is saved on this device.Solution