Same Tree - Practice Coding Problems

Same Tree - Problem

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.

Input & Output

Example 1 — Identical Trees

$ Input: p = [1,2,3], q = [1,2,3]

› Output: true

💡 Note: Both trees have the same structure: root 1 with left child 2 and right child 3. All corresponding nodes have identical values.

Example 2 — Different Structure

$ Input: p = [1,2], q = [1,null,2]

› Output: false

💡 Note: Tree p has node 2 as left child of root 1, while tree q has node 2 as right child of root 1. Different structure makes them not identical.

Example 3 — Different Values

$ Input: p = [1,2,1], q = [1,1,2]

› Output: false

💡 Note: Same structure but different values: p has left=2, right=1 while q has left=1, right=2. Values don't match at corresponding positions.

Constraints

The number of nodes in both trees is in the range [0, 100]
-10⁴ ≤ Node.val ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Trees

Two binary trees p and q to compare

Compare Structure & Values

Check if nodes match at all positions

Output

Return true if identical, false otherwise

Key Takeaway

🎯 Key Insight: Two trees are identical when they have the same structure and all corresponding nodes have equal values

Asked in

G Google 35 a Amazon 28 M Microsoft 22 🍎 Apple 15

The key insight is that two trees are identical if their roots match AND their left/right subtrees are also identical. Best approach is recursive DFS which elegantly handles this by checking current nodes then recursing on children. Time: O(min(m,n)), Space: O(min(m,n))

Common Approaches

Approach	Time	Space	Notes
✓ Recursive DFS Comparison	O(min(m,n))	O(min(m,n))	Recursively compare each node and its children
Breadth-First Search (Level Order)	O(min(m,n))	O(min(m,n))	Use queues to compare trees level by level

Recursive DFS Comparison — Algorithm Steps

Check if both nodes are null (base case)
Check if one is null or values differ
Recursively compare left and right subtrees

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Roots

Check if root values match

Recurse Left

Compare left subtrees recursively

Recurse Right

Compare right subtrees recursively

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

bool solution(struct TreeNode* p, struct TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    if (p->val != q->val) return false;
    return solution(p->left, q->left) && solution(p->right, q->right);
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // For simplicity, assume trees are manually constructed for testing
    struct TreeNode* p = createNode(1);
    p->left = createNode(2);
    p->right = createNode(3);
    
    struct TreeNode* q = createNode(1);
    q->left = createNode(2);
    q->right = createNode(3);
    
    printf(solution(p, q) ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(min(m,n))

Visit each node once until mismatch found, where m and n are tree sizes

✓ Linear Growth

Space Complexity

O(min(m,n))

Recursion call stack depth equals tree height

⚡ Linearithmic Space

312.0K Views

High Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive DFS Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler