Leaf-Similar Trees - Practice Coding Problems

Leaf-Similar Trees - Problem

Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequences are the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Input & Output

Example 1 — Identical Leaf Sequences

$ Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]

› Output: true

💡 Note: Both trees have leaf sequence [6,7,4,9,8] when read from left to right, so they are leaf-similar.

Example 2 — Different Leaf Sequences

$ Input: root1 = [1,2,3], root2 = [1,3,2]

› Output: false

💡 Note: Tree1 has leaves [2,3] while Tree2 has leaves [3,2]. Different order means not leaf-similar.

Example 3 — Single Node Trees

$ Input: root1 = [1], root2 = [1]

› Output: true

💡 Note: Both trees have only one node (which is a leaf) with value 1, so leaf sequences are [1] and [1].

Constraints

The number of nodes in each tree will be in the range [1, 200]
Both of the given trees will have values in the range [0, 200]

Visualization

Tap to expand

Understanding the Visualization

Input Trees

Two binary trees with different internal structures

Extract Leaves

Read leaf values from left to right in both trees

Compare

Check if leaf sequences are identical

Key Takeaway

🎯 Key Insight: Trees are leaf-similar if their leaf value sequences match, regardless of internal structure

Asked in

G Google 25 a Amazon 20 f Facebook 15

The key insight is that only leaf nodes matter for similarity - internal tree structure is irrelevant. We can either collect all leaves first then compare arrays, or use generators to compare leaves on-the-fly. Best approach is simultaneous DFS for memory efficiency. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Simultaneous DFS Comparison	O(n + m)	O(h1 + h2)	Compare leaf values on-the-fly during DFS traversal using generators/iterators
Collect All Leaves Then Compare	O(n + m)	O(h + k)	Extract all leaf values from both trees into arrays, then compare arrays

Simultaneous DFS Comparison — Algorithm Steps

Step 1: Create DFS generators for both trees
Step 2: Iterate through both generators simultaneously
Step 3: Compare each pair of leaf values as they're yielded

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup Iterators

Create DFS generators for both trees

Compare Pairs

Get next leaf from each tree and compare

Early Exit

Stop immediately if any pair doesn't match

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;
};

void getLeaves(struct TreeNode* root, int* leaves, int* size) {
    if (!root) return;
    if (!root->left && !root->right) {
        leaves[(*size)++] = root->val;
        return;
    }
    getLeaves(root->left, leaves, size);
    getLeaves(root->right, leaves, size);
}

bool solution(struct TreeNode* root1, struct TreeNode* root2) {
    int leaves1[1000], leaves2[1000];
    int size1 = 0, size2 = 0;
    
    getLeaves(root1, leaves1, &size1);
    getLeaves(root2, leaves2, &size2);
    
    if (size1 != size2) return false;
    
    for (int i = 0; i < size1; i++) {
        if (leaves1[i] != leaves2[i]) return false;
    }
    
    return true;
}

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

struct TreeNode* buildTree(int* arr, int size) {
    if (size == 0 || arr[0] == -1001) return NULL;
    
    struct TreeNode* root = newNode(arr[0]);
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    int i = 1;
    
    while (front < rear && i < size) {
        struct TreeNode* node = queue[front++];
        
        if (i < size && arr[i] != -1001) {
            node->left = newNode(arr[i]);
            queue[rear++] = node->left;
        }
        i++;
        
        if (i < size && arr[i] != -1001) {
            node->right = newNode(arr[i]);
            queue[rear++] = node->right;
        }
        i++;
    }
    
    return root;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int arr1[100], arr2[100];
    int size1 = 0, size2 = 0;
    
    char* token = strtok(line1, "[],\n ");
    while (token) {
        if (strcmp(token, "null") == 0) {
            arr1[size1++] = -1001;
        } else {
            arr1[size1++] = atoi(token);
        }
        token = strtok(NULL, "[],\n ");
    }
    
    token = strtok(line2, "[],\n ");
    while (token) {
        if (strcmp(token, "null") == 0) {
            arr2[size2++] = -1001;
        } else {
            arr2[size2++] = atoi(token);
        }
        token = strtok(NULL, "[],\n ");
    }
    
    struct TreeNode* root1 = buildTree(arr1, size1);
    struct TreeNode* root2 = buildTree(arr2, size2);
    
    bool result = solution(root1, root2);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Still visit every node, but can potentially exit early on mismatch

✓ Linear Growth

Space Complexity

O(h1 + h2)

Only recursion stack space for both trees, no leaf storage

✓ Linear Space

72.0K Views

Medium Frequency

~15 min Avg. Time

1.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

Simultaneous DFS Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler