Linked List in Binary Tree: Subpath Matching with DFS

You are given the head of a linked list and the root of a binary tree. Return true if all the elements of the linked list, starting from the head, correspond to some downward path connected in the binary tree. In other words, find whether any root-to-leaf or root-to-intermediate path in the tree contains the linked list as a contiguous subpath going only from parent to child.

This is LeetCode 1367: Linked List in Binary Tree, and it sits at the intersection of two fundamental data structures. The trick is not any single algorithm but a clean decomposition into two cooperating recursive functions.

Why this problem matters

Linked List in Binary Tree tests your ability to compose recursive functions. Many tree problems require a single DFS that does everything in one pass. This one is different. You need one function that traverses the tree looking for a starting point, and a second function that tries to extend a match downward from that starting point. Getting this decomposition right is the whole challenge.

The pattern shows up in other problems too: Subtree of Another Tree, Path Sum III, and anywhere you need to "try something at every node." Once you internalize the two-function DFS template, those problems become much easier to reason about.

If you rush and try to do everything in a single recursive call, you will end up tangling the "find a starting node" logic with the "verify the match" logic. Separating them makes the code short, correct, and easy to debug.

The key insight

You need two DFS functions. The first one, isSubPath, visits every node in the tree. At each node, it asks: "Can the entire linked list be matched starting here?" If yes, return true. If no, recurse into the left and right children and try again.

The second function, dfs, takes a linked list node and a tree node and checks whether they match. If the current values match, it advances the linked list pointer and recurses into both children of the tree. If either child continues the match all the way to the end of the list, you are done.

The separation is clean: isSubPath controls where to start matching. dfs controls how to extend a match.

The solution

def isSubPath(head, root):
    if not root:
        return False
    return dfs(head, root) or isSubPath(head, root.left) or isSubPath(head, root.right)

def dfs(head, node):
    if not head:
        return True
    if not node:
        return False
    if head.val != node.val:
        return False
    return dfs(head.next, node.left) or dfs(head.next, node.right)

The isSubPath function is the outer driver. It tries dfs(head, root) at the current tree node. If that fails, it recurses into root.left and root.right to try other starting positions. The short-circuit or means it stops as soon as any attempt succeeds.

The dfs function is the matcher. If the linked list is exhausted (head is None), we matched everything, so return True. If the tree node is None or the values disagree, return False. Otherwise, advance the list pointer and try both children.

Notice how the two functions have different base cases and different recursion patterns, yet they cooperate seamlessly. isSubPath always passes the original head (starting fresh at each tree node), while dfs advances head.next as it progresses through the match.

Visual walkthrough

The outer DFS visits every node in the tree. At each one, it calls the inner matching function. The first two attempts fail (root has value 1, not 4; left child 4 partially matches but runs out of tree before completing the list). The third attempt at right child 4 succeeds because the full chain 4, 2, 1 exists as a downward path.

Complexity analysis

Where n = number of tree nodes, l = linked list length, h = tree height.

For each of the n tree nodes, we might run the dfs matcher, which goes at most min(l, h) levels deep. The space is O(h) for the recursion stack of the outer DFS (the inner DFS adds at most min(l, h) frames, but h already accounts for the deepest possible recursion).

In practice, the early termination from value mismatches means the matcher rarely runs to its full depth, so real-world performance is often much better than the worst case.

The building blocks

1. Tree traversal (DFS to visit every node)

The outer function isSubPath is a standard preorder DFS. It visits the current node, does some work (calls the matcher), and then recurses left and right. This is the same skeleton you use in problems like Maximum Depth of Binary Tree or Invert Binary Tree.

2. Path matching (value-by-value comparison along a downward path)

The inner function dfs walks the tree downward while simultaneously advancing through the linked list. This is similar to the Path Sum pattern, where you subtract from a target as you descend. Here, instead of tracking a running sum, you track a pointer into the linked list.

Edge cases

• Empty linked list (head is None): every tree trivially contains an empty path. Return True.
• Empty tree (root is None): no path exists. Return False (unless the list is also empty).
• Single-node linked list: return True if any node in the tree has the same value.
• List longer than tree height: the matcher will always run out of tree nodes before completing the list. Return False.
• Multiple possible starting points: the outer DFS tries all of them. Even if early attempts fail partway through, a later starting point can still succeed.
• All nodes have the same value: the matcher might get "tricked" into following the wrong branch. It handles this correctly because it tries both left and right children at each step.

From understanding to recall

You have now seen how two cooperating DFS functions solve this problem cleanly. The outer function picks starting points. The inner function verifies the match. It is a small amount of code, and the logic is not complicated. But would you be able to write it from scratch under time pressure?

The gap between "I understand this" and "I can produce this" is the gap that practice closes. The two-function DFS pattern is reusable across many tree problems, so drilling it once gives you leverage on a whole class of questions. You want the decomposition to feel automatic: see a "match something at every node" problem, immediately reach for two functions.

Spaced repetition helps you bridge that gap efficiently. Instead of re-reading the solution five times in one sitting, you write it from memory at increasing intervals. After a few reps, the pattern is yours.

Related posts

• Path Sum - DFS path matching in binary trees
• Subtree of Another Tree - Pattern matching in trees
• Flatten Binary Tree to Linked List - Tree-to-list conversion

The two-function DFS template is one of the most versatile tools in your tree problem toolkit. Once you recognize when a problem calls for it, the implementation follows naturally from the decomposition. Practice it, and you will find it showing up in places you did not expect.