1367. Linked List in Binary Tree
Problem Description
The LeetCode problem presents a scenario where we have two data structures: a binary tree and a linked list. We are asked to determine if the linked list is represented by any downward path in the binary tree. A downward path in the binary tree is defined as a path that starts at any node and extends to subsequent child nodes, going downwards. The path does not need to start at the root of the binary tree. The problem requires us to create a function returning a boolean value: True
if the linked list can be found as a downward path in the binary tree, and False
if it cannot.
Flowchart Walkthrough
Let's use the algorithm flowchart to analyze LeetCode problem 1367, "Linked List in Binary Tree." Here's a detailed examination based on the provided flowchart:
Is it a graph?
- Yes: Though the problem involves a linked list and a binary tree, they can be interpreted as graphs. The binary tree naturally forms a rooted graph structure.
Is it a tree?
- Yes: Despite focusing on both a linked list and a binary tree, the core structure in question — the binary tree — is, by definition, a tree.
DFS
Given that we have identified the subject as a tree, our chart recommends using the Depth-First Search (DFS) as an appropriate algorithm strategy. In this problem, we need to determine if a sequence from the linked list appears in any path of the binary tree. DFS is suited to exploring all potential paths from any given node in the tree to look for a match that represents the sequence from the linked list.
Conclusion:
The flowchart indicates that Depth-First Search (DFS) is the correct approach for this tree-related problem, as it effectively supports a thorough examination of paths that might match the linked list sequence in various branches of the binary tree.
Intuition
To solve this problem, we need to traverse the binary tree and simultaneously compare the values with the nodes in the linked list. As the linked list must be followed in order, we cannot skip nodes in the linked list or in the binary tree's path. The nature of tree traversal and the need to compare it with the linked list suggest a depth-first search (DFS) approach, which allows us to explore a complete path from a node downward before moving to a sibling node.
Here's the intuition behind the solution step by step:
- At each node in the binary tree, we initiate a DFS to check if starting from this node, we can find a path matching the linked list.
- In the DFS, we compare nodes of the binary tree with the linked list in order:
- If the current binary tree node is
None
, it means we've reached the bottom of a path without a mismatch; hence, if we also reached the end of the linked list (head is None
), we've found a matching path. - If the binary tree node's value does not match the current list node's value, the current path is immediately invalid.
- If the values match, we proceed with the next node in both the linked list and continue exploring both subtrees (left and right) of the current binary tree node.
- If the current binary tree node is
- If a full linked list traversal is matched by a downward path in the binary tree (DFS returns
True
), we've found a corresponding path, and we returnTrue
. - If not, we continue checking from the left and right children of the current binary tree node, because the path could start from either subtree.
The proposed solution is recursive in nature. It makes use of a helper function dfs
to handle the downward path checking and calls dfs
repeatedly for each node in the binary tree until a match is found or the entire tree is traversed without finding a corresponding path.
Learn more about Tree, Depth-First Search, Breadth-First Search, Linked List and Binary Tree patterns.
Solution Approach
The provided solution is a recursive algorithm that uses depth-first search (DFS) to solve the problem. Let's break down the important parts of the solution and explain the mechanics step by step:
-
Definition of DFS Helper Function: The
dfs
function is a tailored depth-first search that takes two parameters—the current node of the linked list (head
) and the current node of the binary tree (root
). Its purpose is to check if starting from the current binary tree node, a downward path exists that corresponds to the linked list. -
Base Cases in DFS:
- If the current
head
of the linked list isNone
, this means the linked list has been completely traversed, and thus, a matching path in the tree has been found. The function returnsTrue
in this case. - If the current
root
of the binary tree isNone
or the value of theroot
does not match the value ofhead
, the path being checked does not match the linked list, and the function returnsFalse
.
- If the current
-
Recursive Step in DFS: If the current
head
androot
values match, the algorithm proceeds by checking both the left and right children of the current binary tree node with the next node in the linked list. The dfs function is called recursively for bothroot.left
androot.right
withhead.next
. This recursion propagates downwards through the binary tree, building the downward path. Additionally, a logicalOR
is used between the recursive calls toroot.left
androot.right
, meaning if either subtree contains a matching path, the function will returnTrue
. -
Primary Function Flow:
- If the
root
of the binary tree isNone
, then there cannot be any path that matches the linked list; therefore, it returnsFalse
. - The primary function,
isSubPath
, initializes the process by calling thedfs
function with thehead
of the linked list androot
of the binary tree. - It also calls itself recursively for both
root.left
androot.right
in a similar logicalOR
pattern. This branching out ensures that the algorithm checks all possible starting points in the binary tree for the linked list sequence.
- If the
The use of recursion for both the DFS and the overall traversal of the binary tree nodes enables the algorithm to comprehensively search for the linked list pattern within all downward paths of the tree. This approach is efficient in finding the solution, but it may not be optimal in terms of time complexity due to the multiple recursive calls and the potential for repeating work on overlapping subtrees. However, it is a clear and concise way to solve this particular problem.
Here is the critical section of the code implemented in Python, highlighting the recursive nature of the solution:
1class Solution:
2 def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
3 def dfs(head, root):
4 if head is None:
5 return True
6 if root is None or root.val != head.val:
7 return False
8 return dfs(head.next, root.left) or dfs(head.next, root.right)
9
10 if root is None:
11 return False
12 return (
13 dfs(head, root)
14 or self.isSubPath(head, root.left)
15 or self.isSubPath(head, root.right)
16 )
In summary, the solution leverages recursive DFS to traverse the binary tree and matches each path with the linked list from its starting node to the end of the list to determine if a corresponding downward path exists.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a simple example.
Suppose we have the following binary tree:
1 1 2 / \ 3 4 4 4 / \ 52 6 6 / 7 2
And the given linked list is 4 -> 2
.
Now, let's walk through the solution:
Step 1: Start with the root node of the binary tree
We start with the root, which is node 1, and we compare it to the head of the linked list, which is 4. They do not match, so we proceed to check the left and right children of node 1.
Step 2: Move to the left child of the root node
The left child is node 4, which matches the head of the linked list. Now we invoke the DFS helper function to check for a downward path.
DFS Call for Node 4 (Left Child of Root)
- We check node 4 of the binary tree against the head of the linked list, which is also 4, and there's a match.
- We move to the next element in the linked list (which is 2) and to the left and right children (which are node 2 and
None
, respectively). - Since the left child (node 2) matches the next list element, we continue the DFS call with the next element of the linked list (
None
, since we've reached the end) and the left child of node 2 (which isNone
).
At this point, the linked list has been completely matched with a downward path in the binary tree, and the DFS function returns True
.
The isSubPath
function would return True
, signalling that the linked list 4 -> 2 is indeed a downward path in the binary tree.
If No Match Was Found
If the first DFS call did not return True
, we would continue with other children of the binary tree nodes. For instance, we would also check the right child (node 4) of the root, which again matches the head of the linked list and perform DFS to explore its downward paths.
In this case, although there's another node 4, its children nodes do not continue the sequence with node 2, so the downward path that corresponds to the linked list does not exist on this side of the binary tree.
Following this approach recursively, the solution checks all potential starting nodes in the binary tree and their respective downward paths until a match is found or all possibilities are exhausted.
Solution Implementation
1class ListNode:
2 def __init__(self, value=0, next_node=None):
3 self.value = value
4 self.next_node = next_node
5
6class TreeNode:
7 def __init__(self, value=0, left=None, right=None):
8 self.value = value
9 self.left = left
10 self.right = right
11
12class Solution:
13 def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
14 # Helper function to perform DFS on the binary tree
15 def dfs(linked_list_node, tree_node):
16 # If linked list is fully traversed, a subpath exists
17 if linked_list_node is None:
18 return True
19 # If tree node is None or values don't match, return False
20 if tree_node is None or tree_node.value != linked_list_node.value:
21 return False
22 # Move to next of linked list and left or right child of the tree node
23 return dfs(linked_list_node.next_node, tree_node.left) or dfs(linked_list_node.next_node, tree_node.right)
24
25 # Base case for when the binary tree is empty
26 if root is None:
27 return False
28 # Starting from this root, check for subpath or proceed to its left/right child and repeat
29 return (
30 dfs(head, root)
31 or self.isSubPath(head, root.left)
32 or self.isSubPath(head, root.right)
33 )
34
35# Note: Optional is not imported in this snippet. To use it, add: from typing import Optional
36
1// Definition for singly-linked list.
2class ListNode {
3 int val;
4 ListNode next; // Reference to the next node in the list
5
6 ListNode() {}
7
8 ListNode(int val) { this.val = val; }
9
10 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
11}
12
13// Definition for a binary tree node.
14class TreeNode {
15 int val;
16 TreeNode left; // Reference to the left child node
17 TreeNode right; // Reference to the right child node
18
19 TreeNode() {}
20
21 TreeNode(int val) { this.val = val; }
22
23 TreeNode(int val, TreeNode left, TreeNode right) {
24 this.val = val;
25 this.left = left;
26 this.right = right;
27 }
28}
29
30class Solution {
31 // Checks if there's a subpath in a binary tree that matches the values in a linked list.
32 public boolean isSubPath(ListNode head, TreeNode root) {
33 // If the binary tree is empty, there can't be a subpath.
34 if (root == null) {
35 return false;
36 }
37
38 // Check the current path, or traverse left and right subtree to find the subpath.
39 return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
40 }
41
42 // Helper method using DFS to match the linked list with the path in the binary tree.
43 private boolean dfs(ListNode head, TreeNode root) {
44 // If we've successfully reached the end of the linked list, the subpath is found.
45 if (head == null) {
46 return true;
47 }
48
49 // If the binary tree node is null or values do not match, this path isn't valid.
50 if (root == null || head.val != root.val) {
51 return false;
52 }
53
54 // Continue onto the left or right subtree to find the matching subpath.
55 return dfs(head.next, root.left) || dfs(head.next, root.right);
56 }
57}
58
1/**
2 * Definition for singly-linked list.
3 */
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode() : val(0), next(nullptr) {}
8 ListNode(int x) : val(x), next(nullptr) {}
9 ListNode(int x, ListNode *next) : val(x), next(next) {}
10};
11
12/**
13 * Definition for a binary tree node.
14 */
15struct TreeNode {
16 int val;
17 TreeNode *left;
18 TreeNode *right;
19 TreeNode() : val(0), left(nullptr), right(nullptr) {}
20 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
21 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
22};
23
24class Solution {
25public:
26 // Checks if the linked list is a subpath of the binary tree
27 bool isSubPath(ListNode* head, TreeNode* root) {
28 // If the tree node is null, the list cannot be a subpath
29 if (!root) {
30 return false;
31 }
32 // Check if the list can start from the current tree node or any subtree
33 return depthFirstSearch(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);
34 }
35
36 // Helper function to perform depth-first search starting from a tree node
37 bool depthFirstSearch(ListNode* head, TreeNode* node) {
38 // If list node is null, we've reached the end of the list successfully
39 if (!head) {
40 return true;
41 }
42 // If tree node is null or values don't match, it's not a match
43 if (!node || head->val != node->val) {
44 return false;
45 }
46 // Continue searching the rest of the list in the left and right subtrees
47 return depthFirstSearch(head->next, node->left) || depthFirstSearch(head->next, node->right);
48 }
49};
50
1// This TypeScript code defines two utility functions to determine whether
2// a linked list is a subpath of a binary tree.
3
4/**
5 * This function performs a deep-first search to check if the
6 * current linked list starting at 'head' is a subpath of the binary tree rooted at 'node'.
7 * @param {ListNode | null} head - The current node in the linked list.
8 * @param {TreeNode | null} node - The current node in the binary tree.
9 * @returns {boolean} - Returns true if the list is a subpath from the current tree node, false otherwise.
10 */
11const isSubPathFromNode = (head: ListNode | null, node: TreeNode | null): boolean => {
12 // If the linked list is exhausted, it means we've found a subpath.
13 if (head === null) {
14 return true;
15 }
16 // If the binary tree node is null or the values do not match,
17 // the current path does not match the linked list.
18 if (node === null || head.val !== node.val) {
19 return false;
20 }
21 // Continue the search deeply in both left and right directions of the tree.
22 return isSubPathFromNode(head.next, node.left) || isSubPathFromNode(head.next, node.right);
23};
24
25/**
26 * This function checks if the linked list starting at 'head' is a subpath of the binary tree rooted at 'root'.
27 * It does so by traversing the tree nodes and, for each node, attempting to match the linked list from that starting point.
28 * @param {ListNode | null} head - The head of the linked list.
29 * @param {TreeNode | null} root - The root of the binary tree.
30 * @returns {boolean} - Returns true if the linked list is a subpath of the tree, false otherwise.
31 */
32const isSubPathOfTree = (head: ListNode | null, root: TreeNode | null): boolean => {
33 // If the root of the tree is null, the linked list cannot be a subpath.
34 if (root === null) {
35 return false;
36 }
37 // Check if the linked list is a subpath from the current root node or any of its subtrees.
38 return isSubPathFromNode(head, root) || isSubPathOfTree(head, root.left) || isSubPathOfTree(head, root.right);
39};
40
41// Note that the two methods 'isSubPathFromNode' and 'isSubPathOfTree' are to be used internally,
42// and 'isSubPathOfTree' is the entry point function equivalent to the 'isSubPath' in the original code.
43// The 'isSubPath' name was changed only because the naming convention generally favors descriptive names.
44
Time and Space Complexity
The given code defines a function that checks whether a linked list is a subpath of a binary tree. The complexity is calculated based on two main operations: the dfs
function that performs a deep search to compare a path in the tree with the linked list, and the recursive call isSubPath
to move down the binary tree.
Time Complexity:
The time complexity of the dfs
function is O(N) where N
is the number of nodes in the tree. This is because, in the worst case, it might have to compare every node of the tree with the head of the linked list. Additionally, isSubPath
is called for each node of the tree. Therefore, in the worst case, the time complexity becomes O(N * L) where N
is the number of nodes in the binary tree and L
is the length of the linked list.
Space Complexity:
The space complexity is determined by the maximum depth of the recursive call stack, which would also be proportional to the height of the tree in the worst case. Thus, the space complexity is O(H) where H
is the height of the binary tree. For a skewed tree (one that resembles a linked list), the height of the tree can be N
, making the space complexity O(N) in the worst case.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
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