Given a binary tree root and a linked list with head as the first node.
Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.
In this context downward path means a path that starts at some node and goes downwards.
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 Explanation: 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 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
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.
Constraints:
[1, 2500].[1, 100].1 <= Node.val <= 100 for each node in the linked list and binary tree.Problem Overview: Given a singly linked list and a binary tree, determine whether the linked list exists as a downward path in the tree. The path must follow parent-to-child connections and match the linked list values in order.
Approach 1: Recursive Depth-First Search (O(N*M) time, O(H) space)
This approach treats every tree node as a potential starting point for the linked list. Traverse the tree using DFS. Whenever a node value matches the head of the list, start a secondary recursive check that attempts to match the remaining linked list nodes along the left or right child path. If the match fails, the outer DFS continues searching other nodes in the tree. The key insight is separating the logic into two recursive steps: one that scans the tree and another that validates the linked list path. Time complexity is O(N*M) in the worst case where every tree node starts a partial match attempt, and space complexity is O(H) due to recursion depth of the tree.
This technique relies heavily on Depth-First Search traversal and recursive matching. It works well because binary trees naturally support recursive exploration and branching comparisons.
Approach 2: Iterative Depth-First Search with Stack (O(N*M) time, O(H) space)
The recursive logic can also be implemented iteratively using an explicit stack. First perform a DFS traversal of the tree using a stack to visit each node. When a node matches the linked list head, run an iterative path check that pushes child nodes along with the next linked list node to match. Each stack entry represents a partial state: the current tree node and the corresponding list node. If the list pointer reaches null, the entire linked list has been matched. This avoids recursion while maintaining the same search strategy.
The iterative approach still explores every possible starting node, so the worst‑case time complexity remains O(N*M). Space complexity stays around O(H) for the traversal stack. Developers sometimes prefer this version in environments where recursion depth may cause stack overflow.
The problem combines traversal patterns from Binary Tree problems with sequential comparison from Linked List structures. The difficulty comes from coordinating both structures during traversal.
Recommended for interviews: The recursive DFS solution is the version most interviewers expect. It clearly separates tree traversal from path matching and is concise to implement. Starting with the recursive strategy demonstrates strong understanding of DFS and backtracking. The iterative stack version shows deeper mastery and awareness of recursion limits.
This approach utilizes depth-first search (DFS) recursively to search through the binary tree. For each node that matches the head of the linked list, we will try to match the remaining nodes of the linked list with the children nodes of the current tree node.
We define a helper function isSubPathFromNode to check if a given node in the binary tree can serve as the starting point of a subpath that matches the linked list. It performs a depth-first search recursively. If the current list node matches the tree node, it calls itself on the next list node with both children.
Time Complexity: O(n * m), where n is the number of tree nodes and m is the number of list nodes. Space Complexity: O(h), where h is the height of the tree, due to recursion stack usage.
This strategy employs an iterative depth-first search using an explicit stack to avoid recursion-driven call stacks. We simulate the recursive call stack with a custom stack structure, effectively managing process states iteratively as we check for potential subpaths.
Using an explicit stack to simulate recursion, this C solution handles the depth-first search iteratively. Each stack element consists of a tree node and the matching list node associated with that state. We continuously pop from the stack, testing elements.
Time Complexity: O(n * m), Space Complexity: O(n), where n is the number of nodes in the tree and m is the list node count due to stack usage.
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:
head is empty, it means that the linked list has been traversed, return true;root is empty, it means that the binary tree has been traversed, but the linked list has not been traversed yet, return false;root is not equal to the value of the linked list head, return false;dfs(head.next, root.left) or dfs(head.next, root.right).In the main function, we call dfs(head, root) for each node of the binary tree. As long as one returns true, it means that the linked list is a subpath of the binary tree, return true; if all nodes return false, it means that the linked list is not a subpath of the binary tree, return false.
The time complexity is O(n^2), and the space complexity is O(n). Where n is the number of nodes in the binary tree.
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search | Time Complexity: O(n * m), where n is the number of tree nodes and m is the number of list nodes. Space Complexity: O(h), where h is the height of the tree, due to recursion stack usage. |
| Iterative Depth-First Search with Stack | Time Complexity: O(n * m), Space Complexity: O(n), where n is the number of nodes in the tree and m is the list node count due to stack usage. |
| Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search | O(N*M) | O(H) | Best general solution. Clean recursive logic for checking every starting node in the tree. |
| Iterative DFS with Stack | O(N*M) | O(H) | Useful when avoiding recursion or when working in environments with limited call stack depth. |
Linked List in Binary Tree | Easy | Dry Run | Leetcode 1367 | codestorywithMIK • codestorywithMIK • 11,065 views views
Watch 9 more video solutions →Practice Linked List in Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor