Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree

Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree - Problem

Given a binary tree where each path going from the root to any leaf forms a valid sequence, check if a given string is a valid sequence in such binary tree.

We get the given string from the concatenation of an array of integers arr and the concatenation of all values of the nodes along a path results in a sequence in the given binary tree.

The goal is to determine if there exists a root-to-leaf path in the binary tree where the sequence of node values exactly matches the given array.

Input & Output

Example 1 — Valid Path Exists

$ Input: root = [0,1,0,1,null,6,1], arr = [0,1,1]

› Output: true

💡 Note: The path 0 → 1 → 1 exists in the tree: starting from root(0), go left to node(1), then left again to leaf(1). This matches the sequence [0,1,1].

Example 2 — Path Exists But Not to Leaf

$ Input: root = [0,1,0,1,null,6,1], arr = [0,1]

› Output: false

💡 Note: While the sequence [0,1] exists in the tree (root → left child), it doesn't end at a leaf node. The path must go from root to a leaf.

Example 3 — No Matching Path

$ Input: root = [0,1,0,1,null,6,1], arr = [0,0,1]

› Output: true

💡 Note: The path 0 → 0 → 1 exists: from root(0), go right to node(0), then right again to leaf(1). This matches [0,0,1].

Constraints

1 ≤ nodes.length ≤ 5000
0 ≤ Node.val ≤ 9
1 ≤ arr.length ≤ 5000
0 ≤ arr[i] ≤ 9

Visualization

Tap to expand

Understanding the Visualization

Input Tree & Target

Binary tree [0,1,0,1,null,6,1] and sequence [0,1,1]

Path Matching

Find root-to-leaf paths that match the sequence exactly

Result

Return true if any complete path matches the target sequence

Key Takeaway

🎯 Key Insight: Use DFS with early termination to efficiently check if target sequence exists as complete root-to-leaf path

Asked in

f Facebook 15 a Amazon 12 M Microsoft 8

The key insight is to use DFS with early termination when the current path doesn't match the target sequence. Best approach uses optimized DFS that terminates branches immediately when values don't match. Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS with Early Termination	O(n)	O(h)	Use depth-first search with early termination when sequence doesn't match
Brute Force DFS - Check All Paths	O(n²)	O(n²)	Generate all root-to-leaf paths and check if any matches the target sequence

Optimized DFS with Early Termination — Algorithm Steps

Step 1: Start DFS from root with index 0 of target array
Step 2: At each node, check if current value matches arr[index]
Step 3: If at leaf and index equals array length, return true
Step 4: Recursively explore children with index+1

Visualization

Tap to expand

Step-by-Step Walkthrough

Match Check

At each node, verify if current value matches arr[index]

Early Stop

If values don't match, stop exploring this branch

Leaf Check

At leaf nodes, verify we've matched the complete sequence

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

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

bool dfs(struct TreeNode* node, int* arr, int arrSize, int index) {
    if (!node) return false;
    
    // Early termination if values don't match
    if (index >= arrSize || node->val != arr[index]) {
        return false;
    }
    
    // Check if we're at leaf and matched entire array
    if (!node->left && !node->right) {
        return index == arrSize - 1;
    }
    
    // Explore children
    return dfs(node->left, arr, arrSize, index + 1) || 
           dfs(node->right, arr, arrSize, index + 1);
}

bool solution(struct TreeNode* root, int* arr, int arrSize) {
    if (!root || arrSize == 0) return false;
    return dfs(root, arr, arrSize, 0);
}

int main() {
    // Create example tree: [0,1,0,1,null,6,1]
    struct TreeNode* root = createNode(0);
    root->left = createNode(1);
    root->right = createNode(0);
    root->left->left = createNode(1);
    root->right->left = createNode(6);
    root->right->right = createNode(1);
    
    int arr[] = {0, 1, 1};
    int arrSize = 3;
    
    bool result = solution(root, arr, arrSize);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node at most once, early termination prevents redundant exploration

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h, no extra storage for paths

✓ Linear Space

32.4K Views

Medium Frequency

~15 min Avg. Time

892 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

Optimized DFS with Early Termination — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler