Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree solution and explanation
7 more videos on this problem
Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree | Day 30 LeetCodeKnowledge Center · 17:32 · 6K views
Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree | leetcodethecodingworld · 11:09 · 3K views
Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree - Day 30/30 LeetcodeProgramming Live with Larry · 19:00 · 1K views
Day 30 - Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary TreeHot Rod Gaming · 2:58 · 437 views
Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary TreeCodebix · 12:09 · 416 views
Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary TreeNot An Expert · 10:39 · 370 views
Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree || 30-Day Challengecode Explainer · 6:04 · 301 views
Check If a String Is a Valid Sequence from Root to Leaves Path Day 30 Solution in JAVA,C++,PythonEngineering Library · 7:21 · 365 views
The problem
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 <= 50000 <= 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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isValidSequence(self, root: TreeNode, arr: List[int]) -> bool:
def dfs(root, u):
if root is None or root.val != arr[u]:
return False
if u == len(arr) - 1:
return root.left is None and root.right is None
return dfs(root.left, u + 1) or dfs(root.right, u + 1)
return dfs(root, 0)/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int[] arr;
public boolean isValidSequence(TreeNode root, int[] arr) {
this.arr = arr;
return dfs(root, 0);
}
private boolean dfs(TreeNode root, int u) {
if (root == null || root.val != arr[u]) {
return false;
}
if (u == arr.length - 1) {
return root.left == null && root.right == null;
}
return dfs(root.left, u + 1) || dfs(root.right, u + 1);
}
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isValidSequence(TreeNode* root, vector<int>& arr) {
function<bool(TreeNode*, int)> dfs = [&](TreeNode* root, int u) -> bool {
if (!root || root->val != arr[u]) return false;
if (u == arr.size() - 1) return !root->left && !root->right;
return dfs(root->left, u + 1) || dfs(root->right, u + 1);
};
return dfs(root, 0);
}
};/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidSequence(root *TreeNode, arr []int) bool {
var dfs func(root *TreeNode, u int) bool
dfs = func(root *TreeNode, u int) bool {
if root == nil || root.Val != arr[u] {
return false
}
if u == len(arr)-1 {
return root.Left == nil && root.Right == nil
}
return dfs(root.Left, u+1) || dfs(root.Right, u+1)
}
return dfs(root, 0)
}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 |
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.