Linked List in Binary Tree — Solution in Python, Java & C++
Linked List in Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Linked List in Binary Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the head of a singly linked list and the root of a binary tree.
Return true if the values of the list, from the head onwards, appear in order along some downward path of the tree — a path that starts at any node and moves from parent to child at every step — and false otherwise.
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: The right 4 → its child 2 → that node's child 8 spells 4, 2, 8.
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
Explanation: The downward path 1 → 4 → 2 → 6 starts at the root.
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: 6 and 8 are siblings, so no downward path continues from 6 to 8.
Constraints
1 <= number of list nodes <= 1001 <= number of tree nodes <= 25001 <= Node.val <= 100
Hints for Linked List in Binary Tree
Hint 1
The matching path can start at any tree node, so try every node as a starting point.
Hint 2
From a fixed start, matching is a simple recursion: the current tree node must equal the current list value, then either child must match the rest of the list.
Hint 3
Combine the two:
dfs(node)returns whether a match starts atnode, or inside its left subtree, or inside its right subtree.
How to solve Linked List in Binary Tree
Try each tree node as the start of the path; from a start, follow the list down the tree, branching to either child at each step.
Approach
- Read the list into an array
aof lengthm. match(node, i): ifi == mthe whole list matched — true. Ifnodeis null ornode.val != a[i], false. Otherwise returnmatch(node.left, i + 1) or match(node.right, i + 1).search(node): ifnodeis null, false; elsematch(node, 0) or search(node.left) or search(node.right).- Return
search(root).
Why it works
A downward path is fixed by its first node and the left/right choice at each step. search reaches every possible first node, and match tries both choices at every step while the values agree, so every candidate path is examined and nothing else is accepted.
Complexity
- Time —
O(n · min(m, h)) — each start explores at mostmlevels - Space —
O(h) for the recursion
Pitfalls
- After a mismatch, do not continue the same attempt one node lower — start a fresh attempt from that node instead (that is what
searchdoes). - Equal values on both children: try both branches, not only the first that matches.
Reference solution
Python
from typing import Optional
def isSubPath(head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
a = []
while head:
a.append(head.val)
head = head.next
m = len(a)
def match(node, i):
if i == m:
return True
if node is None or node.val != a[i]:
return False
return match(node.left, i + 1) or match(node.right, i + 1)
def search(node):
if node is None:
return False
return match(node, 0) or search(node.left) or search(node.right)
return search(root)Java
public static boolean isSubPath(ListNode head, TreeNode root) {
List<Integer> list = new ArrayList<>();
for (ListNode cur = head; cur != null; cur = cur.next) list.add(cur.val);
int[] a = new int[list.size()];
for (int i = 0; i < a.length; i++) a[i] = list.get(i);
return searchFrom(root, a);
}
static boolean searchFrom(TreeNode node, int[] a) {
if (node == null) return false;
return matchFrom(node, a, 0) || searchFrom(node.left, a) || searchFrom(node.right, a);
}
static boolean matchFrom(TreeNode node, int[] a, int i) {
if (i == a.length) return true;
if (node == null || node.val != a[i]) return false;
return matchFrom(node.left, a, i + 1) || matchFrom(node.right, a, i + 1);
}C++
bool searchFrom(TreeNode* node, const vector<int>& a);
bool matchFrom(TreeNode* node, const vector<int>& a, size_t i);
bool isSubPath(ListNode* head, TreeNode* root) {
vector<int> a;
for (ListNode* cur = head; cur; cur = cur->next) a.push_back(cur->val);
return searchFrom(root, a);
}
bool searchFrom(TreeNode* node, const vector<int>& a) {
if (!node) return false;
return matchFrom(node, a, 0) || searchFrom(node->left, a) || searchFrom(node->right, a);
}
bool matchFrom(TreeNode* node, const vector<int>& a, size_t i) {
if (i == a.size()) return true;
if (!node || node->val != a[i]) return false;
return matchFrom(node->left, a, i + 1) || matchFrom(node->right, a, i + 1);
}JavaScript
var isSubPath = function(head, root) {
var a = [];
for (var cur = head; cur !== null; cur = cur.next) a.push(cur.val);
return searchFrom(root, a);
};
var searchFrom = function(node, a) {
if (node === null) return false;
return matchFrom(node, a, 0) || searchFrom(node.left, a) || searchFrom(node.right, a);
};
var matchFrom = function(node, a, i) {
if (i === a.length) return true;
if (node === null || node.val !== a[i]) return false;
return matchFrom(node.left, a, i + 1) || matchFrom(node.right, a, i + 1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals