TIC
The Interns Company

Same Tree

EasyAcceptance: 54.7%
TreeDepth-First SearchBreadth-First SearchBinary Tree

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.

Constraints:

  • The number of nodes in both trees is in the range [0, 100]
  • -10^4 <= Node.val <= 10^4

Input Format:

  • Two binary tree roots p and q

Output Format:

  • Return true if the trees are the same, false otherwise.

Examples:

Example 1:

Input:

p = [1,2,3], q = [1,2,3]

Output:

true

Explanation:

Both trees have the same structure and node values.

Example 2:

Input:

p = [1,2], q = [1,null,2]

Output:

false

Explanation:

The trees have different structures.

Example 3:

Input:

p = [1,2,1], q = [1,1,2]

Output:

false

Explanation:

The trees have the same structure but different node values.

Solutions

Recursive DFS Approach

Time: O(n)
Space: O(h)

Use recursion to check if both trees have identical structure and values.

Iterative BFS Approach

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

Use a queue to perform a breadth-first traversal of both trees simultaneously.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Check if the root nodes are both null: false
  2. Check if one root node is null: false
  3. Compare root values: 1 == 1, continue
  4. Check left subtrees recursively:
  5. p.left = 2, q.left = 2, values are the same
  6. p.left.left = null, q.left.left = null, continue
  7. p.left.right = null, q.left.right = null, continue
  8. Check right subtrees recursively:
  9. p.right = 3, q.right = 3, values are the same
  10. p.right.left = null, q.right.left = null, continue
  11. p.right.right = null, q.right.right = null, continue
  12. All nodes match, return true

Hints

Hint 1
Try using recursion to check if both trees have the same structure and values.
Hint 2
Alternatively, you can use iterative approaches like BFS or DFS with a queue or stack.
Hint 3
Remember to check for cases where one tree might be null while the other isn't.

Video Tutorial

Same Tree - Recursive Solution

YouTube•Learn the Same Tree solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the traversal of both binary trees simultaneously, highlighting the matching and non-matching nodes.

Key visualization elements:

  • current node 1
  • current node 2
  • comparison result

Similar Questions

Subtree of Another Tree

Easy

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Asked By

AmazonMicrosoftFacebookGoogleBloombergAdobe

Implementation Notes

This is a foundational binary tree problem that tests understanding of tree traversal and comparison. It's an excellent introduction to recursive DFS on trees.