#1367

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Linked List in Binary Tree

Determine if a linked list is represented as a downward path in a binary tree using pointer traversal and recursive checks efficiently.

linked list tree depth first search binary tree

Problem Statement

Given a binary tree with root node and a singly linked list starting at head, determine whether the linked list's sequence exists along any downward path in the tree. A downward path starts at any node and only moves from parent to child nodes.

Return true if such a path exists where every linked list node corresponds to a consecutive node in the binary tree; otherwise, return false. The challenge focuses on traversing both structures while maintaining list pointer alignment and handling branching in the tree efficiently.

Examples

Example 1

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]

Output: true

Nodes in blue form a subpath in the binary Tree.

Example 2

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]

Output: true

Example details omitted.

Example 3

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]

Output: false

There is no path in the binary tree that contains all the elements of the linked list from head.

Constraints

The number of nodes in the tree will be in the range [1, 2500].
The number of nodes in the list will be in the range [1, 100].
1 <= Node.val <= 100 for each node in the linked list and binary tree.

Solution Approach

Recursive Depth-First Search with Linked List Pointer

Traverse the binary tree recursively. At each node, check if the current node matches the linked list head. If matched, recursively check left and right subtrees for the next list node until the list is exhausted.

Start Matching at Every Tree Node

Because the downward path can start at any tree node, invoke the recursive check for the linked list starting from every tree node. If any invocation returns true, the overall result is true.

Backtracking and Early Termination

If the current tree path fails to match the list, backtrack and try alternate branches. Return immediately when a complete match is found to avoid unnecessary computation, minimizing the exponential search space.

Complexity Analysis

Metric	Value
Time	O(2^{k - 1} \cdot m)
Space	O(n + m)

Time complexity is O(2^{k - 1} * m), where k is the depth of tree and m is the list length, due to potentially exploring both subtrees at each tree node. Space complexity is O(n + m) accounting for tree recursion stack and linked list traversal.

What Interviewers Usually Probe

Focus on traversing both structures simultaneously and maintaining list node alignment.
Consider early termination when a mismatch occurs along a path.
Check edge cases where the linked list starts at leaf nodes or the root.

Common Pitfalls or Variants

Common pitfalls

Failing to start matching at every tree node rather than only at the root.
Incorrectly assuming list nodes can skip tree nodes; all nodes must be consecutive downward.
Ignoring tree null branches, leading to null pointer exceptions during recursion.

Follow-up variants

Check if a circular linked list can be matched along a downward path in a tree.
Determine the longest linked list prefix that matches any path in a binary tree.
Find all paths in the binary tree that exactly match the given linked list sequence.

FAQ

What pattern does 'Linked List in Binary Tree' use?

It uses linked-list pointer manipulation combined with tree traversal, typically implemented with DFS.

Can the linked list start at any node in the binary tree?

Yes, the downward path can start at any tree node; all nodes must match consecutively.

What is the main failure mode for this problem?

Mismatch between linked list nodes and tree nodes along a path is the primary failure mode, requiring backtracking.

How does recursion help solve this problem?

Recursion allows checking each tree node against the current linked list node, exploring all possible downward paths efficiently.

What constraints should be considered for linked list and tree sizes?

The tree can have up to 2500 nodes, and the linked list up to 100 nodes, which affects time and space complexity considerations.

terminal

Solution

Solution 1: Recursion

We design a recursive function $dfs(head, root)$, which indicates whether the linked list $head$ corresponds to a subpath on the path starting with $root$ in the binary tree. The logic of the function $dfs(head, root)$ is as follows:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

# 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
class Solution:
    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        def dfs(head, root):
            if head is None:
                return True
            if root is None or root.val != head.val:
                return False
            return dfs(head.next, root.left) or dfs(head.next, root.right)

        if root is None:
            return False
        return (
            dfs(head, root)
            or self.isSubPath(head, root.left)
            or self.isSubPath(head, root.right)
        )

Continue Practicing

#1372 longest zigzag path in a binary tree #1361 validate binary tree nodes #1373 maximum sum bst in binary tree