We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

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

Number: 1432

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given a binary tree where each root-to-leaf path represents a potential sequence, determine if a given sequence (represented as an array of integers) exists as a valid path in the tree. The sequence is valid only if it matches exactly the values from the root to a leaf node.

Key Insights

  • Use a depth-first search (DFS) approach to traverse the tree while tracking the current index in the sequence.
  • At each node, verify that the node’s value matches the sequence element at the current index.
  • When the end of the sequence is reached, confirm that the current node is a leaf.
  • Return false if the tree path deviates from the sequence at any point.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, since in the worst-case we might traverse all nodes. Space Complexity: O(H), where H is the height of the tree due to the recursion stack.

Solution

We use a recursive DFS to verify the sequence. The algorithm starts at the root and at each recursive call:

  1. Check if the current node is null or if its value does not match the sequence element at the current index; if so, return false.
  2. If the current index is the last element in the sequence, check if the current node is a leaf (i.e., no children). If it is, return true.
  3. Otherwise, recursively call the DFS for the left and right subtrees, advancing the index by one. The recursion stops when a valid path is found or when all possibilities are exhausted.

Code Solutions

# 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:
        # Helper function using DFS
        def dfs(node: TreeNode, index: int) -> bool:
            # If node is None or value doesn't match the sequence, return False
            if not node or node.val != arr[index]:
                return False
            # If we're at the last index, verify if the node is a leaf
            if index == len(arr) - 1:
                return not node.left and not node.right
            # Recursively check left and right subtrees with the next index
            return dfs(node.left, index + 1) or dfs(node.right, index + 1)
        
        return dfs(root, 0)
        
# Example usage:
# root = TreeNode(0, TreeNode(1), TreeNode(0))
# arr = [0,1,0]
# sol = Solution()
# print(sol.isValidSequence(root, arr))
← Back to All Questions