LeetCode 1367 - Linked List in Binary Tree

This problem asks whether a linked list appears as a continuous downward path inside a binary tree. The path does not ne

leetcodemediumlinked-listtreedepth-first-searchbinary-tree

LeetCode Problem 1367

Difficulty: 🟡 Medium
Topics: Linked List, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks whether a linked list appears as a continuous downward path inside a binary tree. The path does not need to start at the root of the tree, but once it starts, it must move only downward through child pointers, either left or right at each step.

The linked list is represented by head, and the binary tree is represented by root. We need to determine whether there exists some tree node such that following a downward path from that node produces exactly the sequence of values in the linked list.

A downward path means:

  • You can start from any node in the tree
  • At each step, you may move to either the left child or the right child
  • You cannot move upward
  • The values along the path must match the linked list in order

For example, if the linked list is:

4 -> 2 -> 8

then we need to find a tree node with value 4, followed by a child path containing 2, followed by a child path containing 8.

The constraints are important:

  • The binary tree has at most 2500 nodes
  • The linked list has at most 100 nodes

These limits are small enough that a recursive depth first search solution is completely feasible. We do not need advanced string matching algorithms like KMP, although such solutions are possible.

Several edge cases are important:

  • The matching path may begin anywhere in the tree, not just the root
  • Multiple nodes can share the same value, so we must explore all possibilities
  • A partial match can fail midway, requiring backtracking
  • The linked list may contain only one node
  • The tree may contain many repeated values, causing many recursive branches
  • A valid path may switch between left and right children during traversal

The problem guarantees that both the tree and linked list contain at least one node.

Approaches

Brute Force Approach

The most direct approach is to treat every tree node as a possible starting point. For each node, we attempt to match the linked list downward using recursion.

The algorithm works in two layers:

  1. Traverse every node in the tree
  2. For each node, recursively check whether the linked list matches a downward path starting there

The matching function compares:

  • Current tree node value
  • Current linked list node value

If they match, it recursively continues into both left and right children.

This approach is correct because every possible starting position is explored, and every possible downward path is checked.

The downside is that many overlapping recursive checks may occur. In the worst case, every tree node may attempt to match nearly the entire linked list.

Still, because the constraints are relatively small, this solution is efficient enough for LeetCode.

Key Insight for the Optimal Approach

The important observation is that the problem naturally separates into two recursive tasks:

  • Searching for a starting point
  • Verifying a matching path

Instead of constructing all possible paths explicitly, we perform recursive matching directly while traversing the tree.

At each tree node:

  • Either this node starts the linked list path
  • Or the matching path exists somewhere in the left subtree
  • Or the matching path exists somewhere in the right subtree

This recursive decomposition keeps the implementation clean and avoids unnecessary storage of paths.

Approach Time Complexity Space Complexity Notes
Brute Force O(N × M) O(H + M) Try matching the linked list from every tree node
Optimal O(N × M) O(H + M) DFS with recursive path matching

Here:

  • N = number of tree nodes
  • M = number of linked list nodes
  • H = height of the tree

Although both approaches have the same asymptotic complexity, the recursive DFS formulation is the cleanest and most practical solution.

Algorithm Walkthrough

  1. Create a helper function matchPath(listNode, treeNode).

This function checks whether the linked list starting at listNode matches a downward tree path starting at treeNode. 2. Handle the base cases inside matchPath.

If listNode becomes None, we successfully matched the entire linked list, so return True.

If treeNode becomes None before the list ends, the path failed, so return False. 3. Compare the current values.

If listNode.val != treeNode.val, the current path cannot continue, so return False. 4. Continue recursively.

If the values match, recursively attempt to match the next linked list node against either:

  • treeNode.left
  • treeNode.right

If either succeeds, return True. 5. Create another DFS function using the main recursion.

This function traverses every node in the tree and treats each node as a potential starting position. 6. At each tree node:

  • Attempt a full path match using matchPath
  • If that fails, recursively search the left subtree
  • If that fails, recursively search the right subtree
  1. If any recursive branch succeeds, return True.
  2. If the entire tree is explored without success, return False.

Why it works

The algorithm is correct because every tree node is considered as a potential starting point, and for each starting point, every valid downward path is explored recursively.

The recursive invariant is:

  • matchPath(listNode, treeNode) returns True if and only if the linked list beginning at listNode exactly matches some downward path beginning at treeNode.

Since the outer DFS checks all possible starting nodes, no valid path can be missed.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def isSubPath(
        self,
        head: Optional[ListNode],
        root: Optional[TreeNode]
    ) -> bool:

        def match_path(
            list_node: Optional[ListNode],
            tree_node: Optional[TreeNode]
        ) -> bool:

            if list_node is None:
                return True

            if tree_node is None:
                return False

            if list_node.val != tree_node.val:
                return False

            return (
                match_path(list_node.next, tree_node.left)
                or
                match_path(list_node.next, tree_node.right)
            )

        if root is None:
            return False

        return (
            match_path(head, root)
            or
            self.isSubPath(head, root.left)
            or
            self.isSubPath(head, root.right)
        )

The implementation contains two recursive layers.

The match_path helper function validates whether the linked list can continue from the current tree node. It first checks whether the list has been fully consumed. If so, the match succeeded. If the tree path ends too early, the match fails.

After confirming the values are equal, the recursion continues into both children because the path may proceed through either subtree.

The outer recursion performs a DFS traversal over the entire tree. Every node becomes a potential starting position for the linked list.

The final return statement combines all three possibilities:

  • The path starts at the current node
  • The path exists somewhere in the left subtree
  • The path exists somewhere in the right subtree

This mirrors the recursive structure of the problem directly.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func isSubPath(head *ListNode, root *TreeNode) bool {

    var matchPath func(*ListNode, *TreeNode) bool

    matchPath = func(listNode *ListNode, treeNode *TreeNode) bool {

        if listNode == nil {
            return true
        }

        if treeNode == nil {
            return false
        }

        if listNode.Val != treeNode.Val {
            return false
        }

        return matchPath(listNode.Next, treeNode.Left) ||
            matchPath(listNode.Next, treeNode.Right)
    }

    if root == nil {
        return false
    }

    return matchPath(head, root) ||
        isSubPath(head, root.Left) ||
        isSubPath(head, root.Right)
}

The Go implementation closely mirrors the Python version.

The primary difference is that Go uses explicit pointer types and nil checks instead of Python's None.

Recursive helper functions are implemented using function variables so they can recursively reference themselves.

Since the node values are small integers, integer overflow is not a concern.

Worked Examples

Example 1

head = [4,2,8]

Tree:

        1
       / \
      4   4
       \  /
        2 2
       /  /
      1  6
        /
       8

We begin DFS traversal from the root.

Current Tree Node Action Result
1 Try matching with 4 Fail
Left 4 Match 4 Continue
2 Match 2 Continue
1 Match 8 Fail
Backtrack Try other branches Continue
Right 4 Match 4 Continue
2 Match 2 Continue
6 Match 8 Fail
8 Match 8 Success

Eventually the algorithm finds:

4 -> 2 -> 8

Therefore the answer is True.

Example 2

head = [1,4,2,6]

The algorithm begins at the root node with value 1.

List Node Tree Node Match
1 1 Yes
4 Left child 4 Yes
2 Child 2 Yes
6 Child 6 Yes

The entire linked list is matched successfully.

Answer: True

Example 3

head = [1,4,2,6,8]

The algorithm successfully matches:

1 -> 4 -> 2 -> 6

but after reaching node 6, no child contains value 8.

Every possible continuation is explored recursively, but all fail.

Therefore the answer is False.

Complexity Analysis

Measure Complexity Explanation
Time O(N × M) Each tree node may attempt to match up to the entire linked list
Space O(H + M) Recursive call stack from tree traversal and path matching

The worst case occurs when many tree nodes share the same value as the linked list head. In that situation, the algorithm repeatedly attempts long partial matches.

The recursive depth is bounded by:

  • Tree height H
  • Linked list length M

Thus the auxiliary space comes entirely from recursion.

Test Cases

# Helper classes
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Helper builders
def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

# Solution under test
class Solution:
    def isSubPath(self, head, root):

        def match_path(list_node, tree_node):

            if list_node is None:
                return True

            if tree_node is None:
                return False

            if list_node.val != tree_node.val:
                return False

            return (
                match_path(list_node.next, tree_node.left)
                or
                match_path(list_node.next, tree_node.right)
            )

        if root is None:
            return False

        return (
            match_path(head, root)
            or
            self.isSubPath(head, root.left)
            or
            self.isSubPath(head, root.right)
        )

solution = Solution()

# Example 1
root1 = TreeNode(
    1,
    TreeNode(4, None, TreeNode(2, TreeNode(1))),
    TreeNode(4, TreeNode(2, TreeNode(6), TreeNode(8)))
)

assert solution.isSubPath(
    build_list([4, 2, 8]),
    root1
) is True  # valid downward path exists

# Example 2
assert solution.isSubPath(
    build_list([1, 4, 2, 6]),
    root1
) is True  # path starts at root

# Example 3
assert solution.isSubPath(
    build_list([1, 4, 2, 6, 8]),
    root1
) is False  # partial match only

# Single-node linked list
single_tree = TreeNode(5)
assert solution.isSubPath(
    build_list([5]),
    single_tree
) is True  # single-node exact match

# No matching values
assert solution.isSubPath(
    build_list([9]),
    single_tree
) is False  # value absent from tree

# Match requires switching branches
branch_tree = TreeNode(
    1,
    TreeNode(2, TreeNode(3)),
    TreeNode(4)
)

assert solution.isSubPath(
    build_list([1, 2, 3]),
    branch_tree
) is True  # left-side chain match

# Repeated values
repeat_tree = TreeNode(
    1,
    TreeNode(1, TreeNode(1)),
    TreeNode(1)
)

assert solution.isSubPath(
    build_list([1, 1]),
    repeat_tree
) is True  # multiple possible starts

# Path interrupted before completion
broken_tree = TreeNode(
    1,
    TreeNode(2),
    TreeNode(3)
)

assert solution.isSubPath(
    build_list([1, 2, 4]),
    broken_tree
) is False  # missing final node

print("All tests passed.")
Test Why
Example 1 Verifies standard matching path
Example 2 Verifies path beginning at root
Example 3 Verifies failed continuation
Single-node linked list Smallest valid linked list
No matching values Ensures mismatch handling
Match requires switching branches Verifies recursive child traversal
Repeated values Tests multiple possible starting points
Path interrupted before completion Ensures partial matches do not incorrectly succeed

Edge Cases

Linked List Contains Only One Node

A single-node linked list is an important edge case because the algorithm should succeed immediately upon finding any matching tree node. Some incorrect implementations assume the path must continue downward and fail unnecessarily.

This implementation handles the case naturally. Once the node values match, the recursive call receives list_node.next == None, which immediately returns True.

Multiple Tree Nodes Share the Same Value

Repeated values can create many possible starting points and overlapping recursive searches. A naive implementation that stops searching after one failed attempt could incorrectly return False.

This solution correctly explores every tree node independently as a starting position. Even if one path fails midway, recursion continues searching elsewhere in the tree.

Partial Match Followed by Failure

A common bug occurs when the linked list partially matches but eventually diverges. For example:

List: 1 -> 2 -> 3
Tree path: 1 -> 2 -> 4

An incorrect implementation might prematurely accept the partial match.

This implementation avoids that issue because success occurs only when the linked list pointer becomes None. Every node in the linked list must be matched exactly in order.