Domain 2MediumMEDIUM

Linked List in Binary Tree

Check if a linked list exists as a downward path in a binary tree by traversing every node to find potential start points and recursively matching the remaining list nodes downwards.

Domain: medium•Updated: 2026-09-15
#DFS#Binary Tree#LinkedList#O(N*M)#Recursion

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: True if a matching path exists, False otherwise.

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.

  1. Tree Traversal: We perform a Depth-First Search (DFS) on the binary tree (dfs function) to visit every node.
  2. Path Matching: For each visited node, we attempt to match the linked list sequence downwards from that specific node (match function).
  3. Pruning: If values mismatch or a child is missing during matching, we stop checking that branch immediately (pruning) to save time.

Approach

  1. 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.
  2. Inside dfs, call a helper function match(current_tree_node, current_list_head).
  3. The match function recursively checks if the remaining part of the linked list can be formed by traversing down from current_tree_node:
    • If we reach the end of the linked list (node_list.next is None), return True.
    • 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).
  4. The main function returns dfs(root), which propagates any success found during traversal up to the caller.

Complexity Analysis

  • Time Complexity: O(N⋅M)O(N \cdot M), where NN is the number of nodes in the tree and MM is the length of the linked list. In the worst case (e.g., all values are identical), we might traverse every node (NN) as a start point and for each, check up to depth MM. Given constraints (2500×100=2.5×1052500 \times 100 = 2.5 \times 10^5 operations), this is efficient enough.
  • Space Complexity: O(H)O(H), where HH is the height of the binary tree. This accounts for the recursion stack used during DFS traversal and matching logic. In a skewed tree, H≈NH \approx N.

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)