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
.
Flowchart Walkthrough
Let's analyze the problem using the Flowchart. We'll go through each decision point step-by-step:
Is it a graph?
- Yes: In this case, the binary tree can be regarded as a type of graph where nodes are connected in a specific structure.
Is it a tree?
- Yes: The problem explicitly mentions a binary tree, which is a type of tree.
DFS
- This point is reached directly after confirming the structure is a tree. A Depth-First Search (DFS) is appropriate for exploring all paths from the root to the leaves in order to check if a given sequence matches any of these paths.
Conclusion: The flowchart leads us to use DFS for this tree problem, as it involves exploring paths from the root to the leaves, aligning perfectly with the intended purpose of Depth-First Search.
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 sequencearr
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 returnTrue
. 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 returnFalse
. - 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.
Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.
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 methodisValidSequence
. This function takes two arguments:root
, representing the current node in the tree, andu
, which is the index of the current element in the sequence arrayarr
. -
Within the
dfs
function, we first check if the current noderoot
isNone
(indicating we've reached a non-existent node beyond the leaf of a path) or if the value ofroot.val
does not match the sequence valuearr[u]
. In either case, we returnFalse
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 conditionroot.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 returnTrue
. -
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)
anddfs(root.right, u + 1)
. Here, we increment the indexu
by1
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 todfs
on the left and right children because a valid sequence can exist in either subtree. If either subtree call returnsTrue
, it means we have a match, and so we returnTrue
for this path.
Here is the implementation of the recursive dfs
function encapsulated in the Solution
class and its method isValidSequence
:
class Solution:
def isValidSequence(self, root: TreeNode, arr: List[int]) -> bool:
def dfs(root, u):
if root is None or root.val != arr[u]:
return False
if u == len(arr) - 1:
return root.left is None and root.right is None
return dfs(root.left, u + 1) or dfs(root.right, u + 1)
return dfs(root, 0)
- The solution overall begins with the call to
dfs(root, 0)
whereroot
is the tree's root node and0
is the starting index of the sequencearr
.
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach, let's consider a small binary tree example and a given sequence to match:
Tree structure: 1 / \ 0 2 / \ 3 4 Sequence 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.
-
We start at the root node with the value
1
. Sincearr[0]
is1
, the first element of the sequence matches the root's value. We proceed to call thedfs
function recursively on both children with the next index (u + 1
), which is1
. -
First, we consider the left child of the root with the value
0
. At this point,arr[1]
is0
, which matches the current node's value. We again proceed with thedfs
function recursively on this node's children. -
For the left child of the node
0
, we have the leaf node with the value3
. The sequence index we're looking for isu + 1 = 2
, which gives usarr[2] = 3
, and it matches the leaf node's value. We check if this is the end of the sequence (sinceu == len(arr) - 1
) and if the current node is a leaf (no children), which is true. -
Considering the conditions are satisfied, the sequence
[1, 0, 3]
is found to be valid, and thedfs
function returnsTrue
.
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.
Solution Implementation
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
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
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
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))
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following shows the order of node visit in a Breadth-first Search?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Want a Structured Path to Master System Design Too? Donāt Miss This!