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

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.