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


Problem Description

In this problem, we are given a binary tree where each root-to-leaf path represents a sequence of numbers corresponding to the values of the nodes along the path. The task is to determine if a given sequence, represented by an array arr, matches any of these root-to-leaf sequences in the binary tree.

The sequence is considered valid if it corresponds exactly to the sequence of node values from the root node to a leaf node. This means that each value in the given array arr must match the value of the corresponding node in the tree as we traverse from the root to a leaf, and the sequence should end at a leaf node.

A leaf node is defined as a node with no children, implying that it doesn’t have a left or right child node. In simple terms, we need to check if there's a path in the given binary tree such that the concatenation of the node values along the path is exactly the same as the given sequence arr.

Intuition

The solution to this problem is based on Depth-First Search (DFS), which is a fundamental traversal algorithm that explores as far as possible along each branch before backtracking. The idea is to traverse the tree from the root, comparing the value at each node with the corresponding element in the given sequence arr.

Here’s the thinking process for arriving at the DFS solution:

  • We start the DFS from the root of the tree.
  • At any given node, we check if the node's value matches the corresponding element in the sequence. If not, we return False because this path can't possibly match the sequence.
  • We also keep track of the index u within the sequence arr that we’re currently checking. We increment this index as we move down the tree to ensure we compare the correct node value with the correct sequence element.
  • If the current node’s value matches the current sequence element and we’re at the last element in the sequence (i.e., u == len(arr) - 1), we check if the current node is also a leaf (it has no children). If it is a leaf, the sequence is valid and we return True. If it’s not a leaf, the sequence is invalid because it hasn't ended at a leaf node.
  • If the current node's value matches the current sequence element but we're not yet at the end of the sequence, we recursively perform DFS on both the left and right children, incrementing the index u.
  • The invocation of DFS on a child node returns True if that subtree contains a path corresponding to the remaining portion of the sequence.
  • If DFS on both the left and right children returns False, this means that there is no valid continuation of the sequence in this part of the tree, and we return False.
  • The initial call to DFS starts with the root node and the first index of the sequence arr.

By applying this approach, we incrementally check each root-to-leaf path against the sequence until we either find a valid path that matches the sequence or exhaust all paths and conclude that no valid sequence exists in the binary tree.

Solution Approach

The implementation of the solution utilizes Depth-First Search (DFS), a classic algorithm often used to explore all paths in a tree or graph until a condition is met or all paths have been explored.

Below are the details of the DFS implementation:

  • We start by defining a recursive function dfs within the method isValidSequence. This function takes two arguments: root, representing the current node in the tree, and u, which is the index of the current element in the sequence array arr.

  • Within the dfs function, we first check if the current node root is None (indicating we've reached a non-existent node beyond the leaf of a path) or if the value of root.val does not match the sequence value arr[u]. In either case, we return False because it means we cannot form the desired sequence along this path.

  • The next crucial check determines if we have reached the end of our sequence with u == len(arr) - 1. If the current node is at this index of the sequence array, we must also verify if it is a leaf. The condition root.left is None and root.right is None confirms whether the current node has no children. If both conditions hold, we have found a valid sequence and return True.

  • If we are not at the end of the sequence, we continue our DFS on both the left and right subtrees by calling dfs(root.left, u + 1) and dfs(root.right, u + 1). Here, we increment the index u by 1 indicating that we're moving to the next element in the sequence as we go one level down the tree.

  • Finally, we use an or operator between the calls to dfs on the left and right children because a valid sequence can exist in either subtree. If either subtree call returns True, it means we have a match, and so we return True for this path.

Here is the implementation of the recursive dfs function encapsulated in the Solution class and its method isValidSequence:

1class Solution:
2    def isValidSequence(self, root: TreeNode, arr: List[int]) -> bool:
3        def dfs(root, u):
4            if root is None or root.val != arr[u]:
5                return False
6            if u == len(arr) - 1:
7                return root.left is None and root.right is None
8            return dfs(root.left, u + 1) or dfs(root.right, u + 1)
9
10        return dfs(root, 0)
  • The solution overall begins with the call to dfs(root, 0) where root is the tree's root node and 0 is the starting index of the sequence arr.

This approach effectively performs a depth-first traversal of the tree, comparing each node's value with the sequence value at the corresponding index. It systematically explores all viable paths down the tree to determine if a valid sequence matching the given array exists.

Example Walkthrough

To illustrate the solution approach, let's consider a small binary tree example and a given sequence to match:

1Tree structure:
2    1
3   / \
4  0   2
5 / \
63   4
7
8Sequence to match: [1, 0, 3]

We want to determine if this sequence can be formed by traversing from the root to a leaf. Now let's perform a walk through using the dfs function step by step.

  1. We start at the root node with the value 1. Since arr[0] is 1, the first element of the sequence matches the root's value. We proceed to call the dfs function recursively on both children with the next index (u + 1), which is 1.

  2. First, we consider the left child of the root with the value 0. At this point, arr[1] is 0, which matches the current node's value. We again proceed with the dfs function recursively on this node's children.

  3. For the left child of the node 0, we have the leaf node with the value 3. The sequence index we're looking for is u + 1 = 2, which gives us arr[2] = 3, and it matches the leaf node's value. We check if this is the end of the sequence (since u == len(arr) - 1) and if the current node is a leaf (no children), which is true.

  4. Considering the conditions are satisfied, the sequence [1, 0, 3] is found to be valid, and the dfs function returns True.

Since the dfs function has found a valid path that matches the given sequence, the entire isValidSequence method would return True. This confirms that the sequence [1, 0, 3] is indeed a root-to-leaf path in the given binary tree.

Python Solution

1class TreeNode:
2    # Definition for a binary tree node.
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def isValidSequence(self, root: TreeNode, sequence: List[int]) -> bool:
10        # Function to perform depth-first search on the tree
11        def dfs(node, index):
12            # Ensure that the current node exists and the value matches the sequence at the current index
13            if not node or node.val != sequence[index]:
14                return False
15
16            # If we are at the last index, check if it's a leaf node
17            if index == len(sequence) - 1:
18                return node.left is None and node.right is None
19
20            # Otherwise, move to the left and right children and increment the index
21            return dfs(node.left, index + 1) or dfs(node.right, index + 1)
22
23        # Begin depth-first search from the root node starting at index 0 of the sequence
24        return dfs(root, 0)
25

Java Solution

1// Definition for a binary tree node.
2class TreeNode {
3    int value; // Node's value
4    TreeNode left; // Reference to the left child
5    TreeNode right; // Reference to the right child
6  
7    TreeNode() {}
8    TreeNode(int value) { this.value = value; }
9    TreeNode(int value, TreeNode left, TreeNode right) {
10        this.value = value;
11        this.left = left;
12        this.right = right;
13    }
14}
15
16class Solution {
17    private int[] sequence; // Array to hold the sequence to validate against the tree nodes
18
19    // Entry method to start the process of validating sequence in the tree
20    public boolean isValidSequence(TreeNode root, int[] sequence) {
21        this.sequence = sequence; // Assign the sequence to the instance variable
22        return isPathExist(root, 0); // Begin depth-first search from the root of the tree
23    }
24
25    // Helper method for depth-first search to validate the sequence
26    private boolean isPathExist(TreeNode node, int index) {
27        // If the current node is null or the value does not match the sequence, return false.
28        if (node == null || node.value != sequence[index]) {
29            return false;
30        }
31        // Check if this node is a leaf and it's the last element in the sequence
32        if (index == sequence.length - 1) {
33            return node.left == null && node.right == null;
34        }
35        // Move to the next index in the sequence and search in both left and right subtrees
36        return isPathExist(node.left, index + 1) || isPathExist(node.right, index + 1);
37    }
38}
39

C++ Solution

1// Definition for a binary tree node.
2struct TreeNode {
3    int val;
4    TreeNode *left;
5    TreeNode *right;
6    TreeNode() : val(0), left(nullptr), right(nullptr) {}
7    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
9};
10
11class Solution {
12public:
13    // Function to determine if a given sequence is a valid path from root to a leaf in the binary tree
14    bool isValidSequence(TreeNode* root, vector<int>& sequence) {
15        // Define a lambda function for depth-first search
16        function<bool(TreeNode*, int)> depthFirstSearch = [&](TreeNode* node, int index) -> bool {
17            // Return false if current node is null or value does not match the sequence at current index
18            if (!node || node->val != sequence[index]) return false;
19          
20            // If we are at the last element of the sequence, we should also be at a leaf node
21            if (index == sequence.size() - 1) return !(node->left) && !(node->right);
22          
23            // Continue the search in the left or right child, incrementing the sequence index
24            return depthFirstSearch(node->left, index + 1) || depthFirstSearch(node->right, index + 1);
25        };
26      
27        // Initial call to depthFirstSearch starting with the root node and the first element of the sequence
28        return depthFirstSearch(root, 0);
29    }
30};
31

Typescript Solution

1// Definition for a binary tree node using TypeScript interfaces
2interface TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6}
7
8// Function to create a new TreeNode with default values
9function createTreeNode(value: number = 0, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode {
10  return {
11    val: value,
12    left: left,
13    right: right
14  };
15}
16
17// Type for the depth-first search function
18type DepthFirstSearchFunction = (node: TreeNode | null, index: number) => boolean;
19
20// Function to determine if a given sequence is a valid path from root to a leaf in the binary tree
21function isValidSequence(root: TreeNode | null, sequence: number[]): boolean {
22  // Define a depth-first search (DFS) function
23  const depthFirstSearch: DepthFirstSearchFunction = (node, index) => {
24    // Return false if current node is null or the value does not match the sequence at the current index
25    if (!node || node.val !== sequence[index]) {
26      return false;
27    }
28  
29    // If we are at the last element of the sequence, we should also be at a leaf node
30    if (index === sequence.length - 1) {
31      return !node.left && !node.right;
32    }
33  
34    // Continue the search in the left or right child, incrementing the sequence index
35    return depthFirstSearch(node.left, index + 1) || depthFirstSearch(node.right, index + 1);
36  };
37
38  // Initial call to DFS starting with the root node and the first element of the sequence
39  return depthFirstSearch(root, 0);
40}
41

Time and Space Complexity

Time Complexity

The time complexity of the code is O(N), where N is the number of nodes in the binary tree. This is because in the worst-case scenario, we will have to visit every node to check if it's a part of the valid sequence. The dfs function is called for every node, but never more than once for a node, so we visit each node a maximum of one time.

Space Complexity

The space complexity of the code is O(H), where H is the height of the binary tree. This is due to the recursive nature of the depth-first search algorithm, which will use stack space for each recursive call. In the worst case (completely unbalanced tree), this could be O(N), if the tree takes the form of a linked list (essentially, each node only has one child). However, in the best case (completely balanced tree), the height of the tree is log(N), and thus the space complexity would be O(log(N)).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫