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

LeetCode Problem 1430

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to determine whether a given array of integers arr represents a valid sequence from the root to a leaf in a binary tree. Each node in the tree has a value between 0 and 9, and a valid sequence is defined as a path starting from the root node down to any leaf node such that the concatenation of node values along that path matches the array arr.

The input consists of a binary tree represented by its root node and an array of integers arr. The output is a boolean: true if arr corresponds to a valid root-to-leaf sequence in the tree, and false otherwise.

Constraints tell us that the array length is at most 5000, and each node value is a single digit, so the tree could be large, but node values are bounded. The edge cases include sequences longer than any root-to-leaf path, sequences that match part of a path but do not end at a leaf, and empty trees or arrays.

Key points to notice:

1. Only root-to-leaf paths count. A sequence matching a non-leaf node is invalid.
2. The length of the sequence must match the depth of the path.
3. Node values and array elements are digits 0-9.

Approaches

The brute-force approach would involve generating all root-to-leaf paths in the tree, converting each path to a sequence, and comparing it with arr. This works because it checks every possibility, but it is inefficient because the number of paths grows exponentially with the height of the tree.

The key insight for a better solution is that we do not need to generate all paths. Instead, we can traverse the tree recursively and compare each node's value with the corresponding element in arr. If the current node's value does not match the current array element, we can stop traversing that path. If we reach a leaf and the last element of arr matches the leaf, we have found a valid sequence. This approach uses depth-first search and is efficient because it prunes paths early when a mismatch occurs.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^h * h)	O(h)	Generate all paths and compare; h is the tree height
Optimal	O(n)	O(h)	DFS with pruning; n is the number of nodes, h is tree height

Algorithm Walkthrough

1. Start from the root node and the first element of arr.
2. If the current node is null, return false because the path cannot continue.
3. Compare the node's value with the current element in arr. If they do not match, return false.
4. If the current node is a leaf (no left or right child) and the index is at the last element of arr, return true.
5. Recursively call the function for the left child and the next element of arr.
6. Recursively call the function for the right child and the next element of arr.
7. Return true if either the left or right recursive call returns true.

Why it works: The recursion maintains the invariant that each node along the path must match the corresponding element in arr. Early pruning ensures efficiency, and checking for leaf nodes guarantees that only complete root-to-leaf paths are considered valid.

Python 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
from typing import Optional, List

class Solution:
    def isValidSequence(self, root: Optional[TreeNode], arr: List[int]) -> bool:
        def dfs(node: Optional[TreeNode], index: int) -> bool:
            if not node:
                return False
            if index >= len(arr) or node.val != arr[index]:
                return False
            if not node.left and not node.right and index == len(arr) - 1:
                return True
            return dfs(node.left, index + 1) or dfs(node.right, index + 1)
        
        return dfs(root, 0)

The Python implementation uses a helper function dfs with two parameters: the current node and the current index in arr. It first handles base cases for null nodes and mismatches. It then checks if the current node is a leaf and the last element matches, returning true if so. Otherwise, it recursively checks both child nodes. This ensures all paths are explored efficiently.

Go Solution

/**
 * 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(node *TreeNode, index int) bool
    dfs = func(node *TreeNode, index int) bool {
        if node == nil {
            return false
        }
        if index >= len(arr) || node.Val != arr[index] {
            return false
        }
        if node.Left == nil && node.Right == nil && index == len(arr)-1 {
            return true
        }
        return dfs(node.Left, index+1) || dfs(node.Right, index+1)
    }
    
    return dfs(root, 0)
}

The Go solution mirrors the Python one. The primary differences are explicit nil checks for child nodes and closure syntax for the recursive helper function. Slice indexing and comparisons follow the same logic as Python.

Worked Examples

Example 1

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

Node	Index	Match	Leaf?	Result
0	0	Yes	No	dfs(left,1) or dfs(right,1)
1	1	Yes	No	dfs(left,2) or dfs(right,2)
0	2	Yes	No	dfs(left,3) or dfs(right,3)
1	3	Yes	Yes	True

Return true.

Example 2

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

Traversal fails because no path matches the sequence, return false.

Example 3

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

Traversal reaches index 2, node value mismatch, return false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited once, and early pruning ensures unnecessary paths are skipped
Space	O(h)	Recursion stack depth corresponds to tree height h

The algorithm efficiently explores only relevant paths, so the overall complexity is linear in the number of nodes. Space complexity is proportional to the height due to recursion.

Test Cases

# Example 1
assert Solution().isValidSequence(
    TreeNode(0, TreeNode(1, TreeNode(0), TreeNode(1, TreeNode(0), TreeNode(0))), TreeNode(0, TreeNode(0), TreeNode(0))),
    [0,1,0,1]
) == True  # valid sequence

# Example 2
assert Solution().isValidSequence(
    TreeNode(0, TreeNode(1, TreeNode(0), TreeNode(1, TreeNode(0), TreeNode(0))), TreeNode(0, TreeNode(0), TreeNode(0))),
    [0,0,1]
) == False  # path does not exist

# Example 3
assert Solution().isValidSequence(
    TreeNode(0, TreeNode(1, TreeNode(0), TreeNode(1, TreeNode(0), TreeNode(0))), TreeNode(0, TreeNode(0), TreeNode(0))),
    [0,1,1]
) == False  # sequence not complete to leaf

# Edge case: single node tree, arr matches
assert Solution().isValidSequence(TreeNode(5), [5]) == True

# Edge case: single node tree, arr does not match
assert Solution().isValidSequence(TreeNode(5), [0]) == False

# Edge case: longer arr than path
assert Solution().isValidSequence(TreeNode(1, TreeNode(2)), [1,2,3]) == False

Test	Why
[0,1,0,1]	Valid root-to-leaf sequence
[0,0,1]	Path does not exist
[0,1,1]	Sequence incomplete (not leaf)
[5]	Single node tree matching
[0]	Single node tree mismatch
[1,2,3]	Sequence longer than any path

Edge Cases

Single-node tree: If the tree has only one node, the array must match exactly. Otherwise, it is invalid. This ensures that both leaf and root-only paths are handled correctly.

Array longer than any path: If arr is