Same Tree

Google Interview Question

📢 Poll of the Day

---

🎥 Video Solution

---

Problem Overview

Difficulty: Easy

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

Example 1

Input:
· p = Node(1)
· q = Node(1)

Output: 
· False

Explanation:
· Values are same
· But structures are different
· So we return False

Example 2

Input:
· p = Node(1)
· q = Node(1)

Output: 
· True

Explanation:
· Values are same
· Structures are same
· So we return True

---

Step 1: Clarify Requirements

• What does "same tree" mean?

  • Same values and same structure.

• Can the given roots be empty?

  • Yes, return True if both are empty.

• Are the node values unique?

  • No, they can be the same.

---

Step 2: Discuss Approaches

🟡 Approach 1: Serialize Trees to Strings

• Logic:

  • Convert both trees to a string

  • Compare the two strings

  • Make sure to serialize null values

• Big O:

  • Time Complexity: O(p + q)

  • Space Complexity: O(p + q)

🟢 Approach 2: Preorder Traversal (Optimal)

• Logic:

  • Return True if both nodes are null

  • Return False if:

    • Only one node is null

    • Or if values don’t match

  • Compare subtrees recursively

• Big O:

  • Time Complexity: O(min(p, q))

  • Space Complexity: O(min(p, q))

---

Step 3: Write Code (Optimal)

Python

---

Java

---

C++

---

Step 4: Answer Follow-Ups

• What if the trees are very deep?

  • Recursion can cause stack overflow.

  • Use an iterative approach instead.

• What if node values are not unique?

  • Our algorithm still works fine.

  • It correctly handles duplicates also.

• What if we have n-ary trees?

  • Need to check two things:

    • Number of children.

    • Children values in order.

  • Return False if either differs.

---

🎥 Join Me on YouTube

• Watch interview-prep videos

• Join Here: YouTube URL

---

🤝 Join Me on LinkedIn

• 40K+ strong community

• Join Here: LinkedIn URL

---

👨‍💻 Need Interview Practice?

• Book a 1:1 with me

• Book Here: Booking URL