Problem Breakdown
We need to determine if there is any continuous downward path within a Binary Tree that matches the sequence of values in a given Linked List. A “downward” path means moving from parent to child (left or right) without skipping nodes or changing direction upwards/sideways. The solution must return True immediately upon finding any valid instance, otherwise False.
Inputs:
root: Root node of the Binary Tree (TreeNode).head: Head node of the Linked List (ListNode).
Outputs:
- Boolean:
Trueif a matching path exists,Falseotherwise.
Intuition
The problem requires checking for a specific sequence within a tree structure where directionality is constrained (parent to child). Since we don’t know which node in the tree starts this sequence, every node must be considered as a potential starting point.
- Tree Traversal: We perform a Depth-First Search (DFS) on the binary tree (
dfsfunction) to visit every node. - Path Matching: For each visited node, we attempt to match the linked list sequence downwards from that specific node (
matchfunction). - Pruning: If values mismatch or a child is missing during matching, we stop checking that branch immediately (pruning) to save time.
Approach
- Define an outer DFS traversal
dfs(node)which iterates through all nodes in the binary tree. This ensures every node acts as a candidate start for the linked list path. - Inside
dfs, call a helper functionmatch(current_tree_node, current_list_head). - The
matchfunction recursively checks if the remaining part of the linked list can be formed by traversing down fromcurrent_tree_node:- If we reach the end of the linked list (
node_list.next is None), returnTrue. - If the current tree node value doesn’t match or a child is missing, stop this branch.
- Recursively check both left and right children with the next node in the linked list (using logical OR).
- If we reach the end of the linked list (
- The main function returns
dfs(root), which propagates any success found during traversal up to the caller.
Complexity Analysis
- Time Complexity: , where is the number of nodes in the tree and is the length of the linked list. In the worst case (e.g., all values are identical), we might traverse every node () as a start point and for each, check up to depth . Given constraints ( operations), this is efficient enough.
- Space Complexity: , where is the height of the binary tree. This accounts for the recursion stack used during DFS traversal and matching logic. In a skewed tree, .
Solution
class Solution:
def isSubPath(self, head: 'ListNode', root: 'TreeNode') -> bool:
"""
Determines if the linked list starting at `head` exists as a downward path
in the binary tree rooted at `root`.
Args:
head (ListNode): Head of the linked list.
root (TreeNode): Root of the binary tree.
Returns:
bool: True if subpath found, False otherwise.
"""
# Helper function to check if the remaining part of the linked list
# matches a downward path starting from `node_tree` downwards.
def match(node_tree, node_list):
# If we've successfully traversed all nodes in the linked list, return True
if not node_list:
return True
# Stop recursion if tree is exhausted or values don't match at current step
if not node_tree or node_tree.val != node_list.val:
return False
# Recurse on both children with the next node in the linked list.
# We need a path, so either left OR right must succeed.
return self.match(node_tree.left, node_list.next) \
or self.match(node_tree.right, node_list.next)
def dfs(tree_node):
if not tree_node:
return False
# Check if the linked list starts matching at this specific tree node
if match(tree_node, head):
return True
# If current node isn't a start point (or failed), continue searching
# in subtrees. The path could be entirely within left or right subtree.
return dfs(tree_node.left) or dfs(tree_node.right)
return dfs(root)