This problem requires verifying whether a linked list is embedded in a binary tree along a downward path. The key is to recursively traverse the tree, matching nodes to the linked list in order. Failure occurs when list nodes diverge from the tree path, so careful pointer manipulation and DFS tracking are crucial to ensure correctness and efficiency.
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.
How GhostInterview Helps
- GhostInterview provides step-by-step pointer tracking to ensure linked list nodes align with tree nodes.
- It highlights mismatches early and guides backtracking when paths fail, reducing wasted traversal.
- Offers visual cues of tree paths versus list sequence to clarify recursive DFS matching.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Linked List in Binary Tree instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Linked List in Binary Tree from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the longest ZigZag path in a binary tree using depth-first search and dynamic programming for precise node state tracking.
Open problem page#1361 Validate Binary Tree NodesValidate Binary Tree Nodes problem requires checking if a set of nodes forms a valid binary tree using graph traversal.
Open problem page#1373 Maximum Sum BST in Binary TreeFind the maximum sum of values from any Binary Search Tree (BST) subtree in a binary tree.
Open problem page