What is the time complexity of Same Tree?

The optimal solution has a time complexity of O(n).

What is the space complexity of Same Tree?

The space complexity is O(log n).

What data structures are used to solve Same Tree?

This problem uses Tree, Depth-First Search, Breadth-First Search, Binary Tree. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Same Tree?

The problem's definition of 'sameness' is inherently recursive: two trees are identical if their roots match AND their corresponding subtrees recursively match. This makes a recursive DFS traversal the most natural and clean algorithmic fit. Handling `null` (or `None`) nodes is paramount for establishing structural identity. The solution carefully differentiates between both nodes being `null` (structurally identical empty branches), and one being `null` while the other is not (an immediate structural mismatch, e.g., `p` has a left child but `q` doesn't).

Which companies ask LeetCode 100. Same Tree in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Bloomberg, Flipkart and 6 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Same Tree - LeetCode 100 Solution

Q: How to solve Same Tree?

The most intuitive and elegant approach for this problem leverages the recursive nature of binary trees themselves, using a Depth-First Search (DFS) strategy. The core idea is to break down the problem: two trees are the same if and only if their current nodes are identical (both null, or both non-null with matching values), AND their left subtrees are identical, AND their right subtrees are identical. The provided solution directly implements this principle. It starts by comparing the roots: if both are null, they are trivially the same. If only one is null, they are structurally different. If both exist but have different values, they are also different. Only if all these checks pass do we recursively apply the *exact same logic* to their left children and their right children. The `and` operator ensures that *both* left and right subproblems must return true for the current subproblem to be considered true, effectively short-circuiting and returning `false` as soon as any mismatch is found anywhere in the tree.

Same Tree - Complete Solution Guide

Same Tree is LeetCode problem 100, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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

Detailed Explanation

This problem challenges us to determine if two given binary trees, `p` and `q`, are fundamentally identical. What does 'identical' mean here? It's not just about having the same set of values, but rather a strict combination of structural congruence and matching node values at every corresponding position. For instance, if `p` has a left child with value 2 and `q` has a left child with value 2, that's a match. But if `p` has a left child and `q` has *no* left child (or a `null` child), they are immediately different, regardless of what other nodes might exist. This is perfectly illustrated by Example 2, where `p = [1,2]` (a root 1 with a left child 2) and `q = [1,null,2]` (a root 1 with a right child 2). Despite having the same values, their structures diverge right after the root, making them unequal.

Solution Approach

The most intuitive and elegant approach for this problem leverages the recursive nature of binary trees themselves, using a Depth-First Search (DFS) strategy. The core idea is to break down the problem: two trees are the same if and only if their current nodes are identical (both null, or both non-null with matching values), AND their left subtrees are identical, AND their right subtrees are identical. The provided solution directly implements this principle. It starts by comparing the roots: if both are null, they are trivially the same. If only one is null, they are structurally different. If both exist but have different values, they are also different. Only if all these checks pass do we recursively apply the *exact same logic* to their left children and their right children. The `and` operator ensures that *both* left and right subproblems must return true for the current subproblem to be considered true, effectively short-circuiting and returning `false` as soon as any mismatch is found anywhere in the tree.

Step-by-Step Algorithm

Step 1: Check if both `p` and `q` are `null` (or `None`). If so, return `true` (both trees are empty and identical).
Step 2: Check if either `p` or `q` is `null` (or `None`). If so, return `false` (one tree is empty, the other is not).
Step 3: Check if the values of the root nodes (`p.val` and `q.val`) are different. If so, return `false`.
Step 4: Recursively call `isSameTree` on the left subtrees (`p.left` and `q.left`) and the right subtrees (`p.right` and `q.right`).
Step 5: Return `true` only if both recursive calls in step 4 return `true`; otherwise, return `false`.

Key Insights

The problem's definition of 'sameness' is inherently recursive: two trees are identical if their roots match AND their corresponding subtrees recursively match. This makes a recursive DFS traversal the most natural and clean algorithmic fit.
Handling `null` (or `None`) nodes is paramount for establishing structural identity. The solution carefully differentiates between both nodes being `null` (structurally identical empty branches), and one being `null` while the other is not (an immediate structural mismatch, e.g., `p` has a left child but `q` doesn't).
Early exit conditions (short-circuiting) are crucial for efficiency. As soon as any structural difference (one node is `null`, the other isn't) or value mismatch is detected at any level, the function immediately returns `False`. There's no need to continue traversing deeper into branches that are already confirmed to be different.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(log n)

Topics

This problem involves: Tree, Depth-First Search, Breadth-First Search, Binary Tree.

Companies

Asked at: Adobe, Amazon, Apple, Bloomberg, Flipkart, Google, LinkedIn, Meta, Microsoft, Yahoo, tcs.

Same Tree | LeetCode 100

Easy

Tree Depth-First Search Breadth-First Search Binary Tree

Time: O(n)Space: O(log n)

Solution Code

Available in:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 100: Same Tree - Detailed explanation and solution approaches.

Topics

Tree Depth-First Search Breadth-First Search Binary Tree

Companies

AdobeAmazonAppleBloombergFlipkartGoogleLinkedInMeta

Stats

Difficulty:Easy

Languages:4

Companies:11

Problem #:100

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Check if both `p` and `q` are `null` (or `None`). If so, return `true` (both trees are empty and identical).
2
Step 2: Check if either `p` or `q` is `null` (or `None`). If so, return `false` (one tree is empty, the other is not).
3
Step 3: Check if the values of the root nodes (`p.val` and `q.val`) are different. If so, return `false`.
4
Step 4: Recursively call `isSameTree` on the left subtrees (`p.left` and `q.left`) and the right subtrees (`p.right` and `q.right`).
5
Step 5: Return `true` only if both recursive calls in step 4 return `true`; otherwise, return `false`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(log n)

🎯 Logarithmic space - Very memory efficient!

📝

Why?

Each node is visited at most once during the recursive traversal, leading to a linear time complexity. The space used is proportional to the depth of recursion, which is logarithmic in a balanced tree and linear in a skewed tree.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Iterative Breadth-First Search (BFS)

Use a queue to perform a level-order traversal of both trees simultaneously, comparing nodes at each level.

Time: O(n)Space: O(w), where w is the maximum width of the tree (can be O(n) in a skewed tree, or O(log n) for a balanced tree).

Trade-offs: BFS uses more space compared to DFS, especially in wide trees, but might offer slightly better performance for certain tree structures due to the iterative nature, avoiding the overhead of recursive function calls.

✨

Key Insights

1The problem's definition of 'sameness' is inherently recursive: two trees are identical if their roots match AND their corresponding subtrees recursively match. This makes a recursive DFS traversal the most natural and clean algorithmic fit.
2Handling `null` (or `None`) nodes is paramount for establishing structural identity. The solution carefully differentiates between both nodes being `null` (structurally identical empty branches), and one being `null` while the other is not (an immediate structural mismatch, e.g., `p` has a left child but `q` doesn't).
3Early exit conditions (short-circuiting) are crucial for efficiency. As soon as any structural difference (one node is `null`, the other isn't) or value mismatch is detected at any level, the function immediately returns `False`. There's no need to continue traversing deeper into branches that are already confirmed to be different.

📚

Key Terms Explained

For Students

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: Empty trees: The solution correctly handles the case where both trees are empty, returning `true`.
Edge case 2: One tree is empty: The solution correctly handles the case where one tree is empty and the other is not, returning `false`.
Edge case 3: Trees with different structures: The recursive calls effectively detect trees with differing structures at any depth.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting base cases: Failing to handle the `null` or `None` cases properly leads to infinite recursion and stack overflow errors.

✗Common mistake 2: Incorrect conditional logic: Improperly comparing node values or combining the results of recursive calls can result in wrong comparisons.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Comparing the structure of XML or JSON documents that represent hierarchical data. This algorithm could be adapted to check if two such documents have identical structures.

🏦Real-world scenario 2: Version control systems can use tree comparison to identify changes in the file system between commits. This is a simplified model, but the core principle of comparing tree structures applies.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Most tree problems can be solved recursively. The base case is usually a null node. Think about what information needs to flow up vs down the tree.

🎯 Interview Tip

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ Watch Out

Not handling null nodes properly. Always check if the current node exists before accessing its children.

👨‍💻 From Experience

This is one of the first problems I solved when learning Tree. It's a great foundation for more complex problems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 9, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 14

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 7

❓

Frequently Asked Questions

How do I choose between recursive and iterative tree traversal?

Use recursive traversal for cleaner code when stack depth isn't a concern (tree height < ~1000). Use iterative with explicit stack for very deep trees to avoid stack overflow. Iterative is also preferred when you need fine-grained control over the traversal process.

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Same Tree"?

For this easy-level Tree problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether depth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?