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

Q: Is Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree easy or hard?

The problem is rated Medium because it combines tree traversal with path validation logic. The traversal itself is standard DFS, but correctly handling the array index and ensuring the path ends at a leaf requires careful boundary checks.

Q: Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree Python/Java solution

Python and Java implementations usually rely on recursive DFS. The function compares the current node value with the array element, then recursively checks the left and right subtrees with the next index. The path is valid only if the final array element matches a leaf node. Time complexity is O(n) with O(h) recursion space.

Q: How to solve Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree in O(n)?

Use a DFS traversal starting from the root and track the index in the array. At each node, check whether the node value matches arr[index]. If it does, continue recursively with index + 1. When you reach the last array element, return true only if the node is a leaf. This ensures every node is processed once, giving O(n) time complexity.

Q: What is the best approach for Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree?

Depth-First Search (DFS) is the most effective approach. Traverse the tree from the root while matching each node value with the corresponding element in the array. When you reach the final array element, confirm that the current node is a leaf. This solution runs in O(n) time with O(h) space for the recursion stack.

Q: Is Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree asked at Google/Amazon/Meta?

Variants of root-to-leaf path validation problems appear frequently in interviews at companies like Amazon, Google, and Meta. Interviewers often use them to test understanding of tree traversal, recursion, and path validation logic using DFS.

Q: What data structure is used in Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree?

The core data structure is a binary tree. The solution typically uses recursion or an explicit stack/queue for traversal. DFS uses the call stack to track the path, while BFS implementations use a queue storing nodes and the current index in the array.

Q: What is the time complexity of Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree?

The optimal solution runs in O(n) time where n is the number of nodes in the tree. Each node is visited at most once during traversal. Space complexity is O(h) for recursive DFS due to the call stack, where h is the height of the binary tree.

MediumPremiumFree on FleetCodeTree Depth-First Search Breadth-First Search Binary Tree5 min read

Practice this problem

Problem Statement

Given a binary tree where each path going from the root to any leaf form 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.

Example 1:

Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1]
Output: true
Explanation: 
The path 0 -> 1 -> 0 -> 1 is a valid sequence (green color in the figure). 
Other valid sequences are: 
0 -> 1 -> 1 -> 0 
0 -> 0 -> 0

Example 2:

Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,0,1]
Output: false 
Explanation: The path 0 -> 0 -> 1 does not exist, therefore it is not even a sequence.

Example 3:

Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,1]
Output: false
Explanation: The path 0 -> 1 -> 1 is a sequence, but it is not a valid sequence.

Constraints:

1 <= arr.length <= 5000
0 <= arr[i] <= 9
Each node's value is between [0 - 9].

Approach Overview

Problem Overview: You are given a binary tree and an integer array. The task is to check whether the array represents a valid path starting from the root and ending exactly at a leaf node. Each element in the array must match the node values along the path, and the path must terminate at a leaf.

Approach 1: Depth-First Search Path Matching (O(n) time, O(h) space)

The most direct solution uses recursive Depth-First Search. Start from the root and compare the current node value with the corresponding element in the array. If they match, recursively explore the left and right children while advancing the index in the array. The key condition is that when you reach the last element of the array, the current node must also be a leaf node. If the node value mismatches or the array index exceeds bounds, the path is invalid and you backtrack.

This approach works because DFS naturally follows root-to-leaf paths in a binary tree. Each recursive call verifies one step in the sequence, and the search stops early when a mismatch occurs. The algorithm visits each node at most once in the worst case, giving O(n) time complexity where n is the number of nodes. The recursion stack uses O(h) space, where h is the tree height.

Approach 2: Breadth-First Search with Index Tracking (O(n) time, O(n) space)

An iterative alternative uses Breadth-First Search. Maintain a queue storing pairs of (node, index), where index represents the position in the array that must match the node's value. Start with the root and index 0. When processing a node, check if its value equals arr[index]. If it does not match, discard that path. If it matches and the node is a leaf while index is the last array position, a valid sequence exists.

If the sequence is not finished, push the node's children into the queue with index + 1. BFS explores multiple candidate paths simultaneously and guarantees that every valid root-to-leaf candidate is examined. The time complexity remains O(n) because each node is processed once, but the queue can store many nodes at the same level, resulting in O(n) auxiliary space in the worst case.

Recommended for interviews: The recursive DFS solution is what interviewers typically expect. It directly models the root-to-leaf path validation and keeps the code concise. Mentioning BFS as an alternative demonstrates that you understand multiple traversal strategies in tree problems. DFS is usually preferred because it uses less memory and aligns naturally with path-based checks.

Solution

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
DFS Recursive Path Matching	O(n)	O(h)	Best general solution for validating root-to-leaf paths with minimal memory
BFS with Queue and Index Tracking	O(n)	O(n)	Useful when exploring multiple candidate paths iteratively or avoiding recursion

Video Solution

Valid sequence from root to leaf in a binary tree | Leetcode • Techdose • 7,009 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree easy or hard?

The problem is rated Medium because it combines tree traversal with path validation logic. The traversal itself is standard DFS, but correctly handling the array index and ensuring the path ends at a leaf requires careful boundary checks.

Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree Python/Java solution

Python and Java implementations usually rely on recursive DFS. The function compares the current node value with the array element, then recursively checks the left and right subtrees with the next index. The path is valid only if the final array element matches a leaf node. Time complexity is O(n) with O(h) recursion space.

How to solve Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree in O(n)?

Use a DFS traversal starting from the root and track the index in the array. At each node, check whether the node value matches arr[index]. If it does, continue recursively with index + 1. When you reach the last array element, return true only if the node is a leaf. This ensures every node is processed once, giving O(n) time complexity.

What is the best approach for Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree?

Depth-First Search (DFS) is the most effective approach. Traverse the tree from the root while matching each node value with the corresponding element in the array. When you reach the final array element, confirm that the current node is a leaf. This solution runs in O(n) time with O(h) space for the recursion stack.

Is Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree asked at Google/Amazon/Meta?

Variants of root-to-leaf path validation problems appear frequently in interviews at companies like Amazon, Google, and Meta. Interviewers often use them to test understanding of tree traversal, recursion, and path validation logic using DFS.

What data structure is used in Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree?

The core data structure is a binary tree. The solution typically uses recursion or an explicit stack/queue for traversal. DFS uses the call stack to track the path, while BFS implementations use a queue storing nodes and the current index in the array.

What is the time complexity of Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree?

The optimal solution runs in O(n) time where n is the number of nodes in the tree. Each node is visited at most once during traversal. Space complexity is O(h) for recursive DFS due to the call stack, where h is the height of the binary tree.

Ready to solve this problem?

Practice Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree with our built-in code editor and test cases.

Practice on FleetCode

Binary Tree Inorder Traversal

Unique Binary Search Trees II

Problem Info

DifficultyMedium

Acceptance47.6%

Approaches1

Reading time5 min