Check If A String Is A Valid Sequence From Root To Leaves Path In A Binary Tree - Leetcode Solution

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 a string as input and we have to check whether it forms a valid sequence from the root to the leaves in the binary tree or not.

Solution:

We will solve this problem recursively by traversing the tree in a pre-order traversal. Pre-order traversal of binary tree means, visiting the root node first, then the left subtree, and finally the right subtree.

At each node, we check if the current node is a leaf node and if we have reached the end of the input string. If both conditions are true, we return True as the input string is valid. If any of the two conditions fails, we move on to the next node.

If the current node is not a leaf node, we will check if there are any characters left in the input string. If there are no characters left, the input string is not valid, as there are more nodes to be traversed in the binary tree.

If there are characters left in the input string, we check if the value of the current node matches the current character of the input string. If it matches, we will recursively call the same function for the left and the right child nodes.

If we reach the end of the tree and end of the input string is also reached, we return True. Otherwise, we return False.

Pseudo-code:

1. If the input rootnode is None and len(string) is 0, return True.
2. If the input rootnode is None or len(string) is 0, return False.
3. If the input rootnode value is not equal to the first character of the string, return False.
4. If input rootnode is a leaf node and len(string) is 1, return True.
5. Recursively check the left and right child nodes of the rootnode, passing string[1:] as the string to check.
6. If either recursive call returns True, return True, otherwise return False.

Python Code:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

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

Time Complexity: O(n)

Space Complexity: O(h)

where n is the number of nodes in the binary tree and h is the height of the binary tree.

Testing:

We can test the solution using the test case given below:

Example:

root = TreeNode(0) root.left = TreeNode(1) root.left.left = TreeNode(0) root.left.right = TreeNode(1) root.left.right.left = TreeNode(0) root.left.right.right = TreeNode(0) root.right = TreeNode(0) root.right.left = TreeNode(0)

arr = [0, 1, 0, 1]

output = True

Solution:

Output of the above test case is True, which is the expected output.

Conclusion:

We have solved the "Check If A String Is A Valid Sequence From Root To Leaves Path In A Binary Tree" problem on LeetCode using a recursive approach. The time complexity of our solution is O(n), where n is the number of nodes in the binary tree and the space complexity is O(h), where h is the height of the binary tree.

1