Skip to main content
Talentd

Linked List in Binary Tree - Solution & Explanation

MediumLinked ListTreeDepth-First SearchBinary Tree24 min readAsked at: Amazon, Meta, Google +2
Practice this problem

Problem Statement

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:

  • 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.

Approach Overview

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.

Approach 1: Recursive Depth-First Search

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Iterative Depth-First Search with Stack

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: 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:

  • If the linked list head is empty, it means that the linked list has been traversed, return true;
  • If the binary tree root is empty, it means that the binary tree has been traversed, but the linked list has not been traversed yet, return false;
  • If the value of the binary tree root is not equal to the value of the linked list head, return false;
  • Otherwise, return 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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Depth-First SearchO(N*M)O(H)Best general solution. Clean recursive logic for checking every starting node in the tree.
Iterative DFS with StackO(N*M)O(H)Useful when avoiding recursion or when working in environments with limited call stack depth.

Video Solution

Linked List in Binary Tree | Easy | Dry Run | Leetcode 1367 | codestorywithMIK • codestorywithMIK • 11,612 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Linked List in Binary Tree easy or hard?
Linked List in Binary Tree is considered a Medium difficulty problem on LeetCode. The logic itself is straightforward, but coordinating recursive traversal with linked list matching can be tricky for developers unfamiliar with DFS patterns.
Linked List in Binary Tree Python/Java solution
Python and Java implementations usually define a helper function that checks whether a linked list path matches from the current tree node. The main function performs DFS across the tree and calls the helper whenever node values match the list head.
How to solve Linked List in Binary Tree in O(n)?
The typical interview solution runs in O(N*M). Achieving strict O(N) would require advanced string matching techniques such as KMP applied to tree traversal sequences, but that approach is rarely expected in interviews. Most solutions rely on DFS with path matching.
What is the best approach for Linked List in Binary Tree?
The most common approach uses Depth-First Search with recursion. Traverse each tree node as a potential starting point and recursively verify whether the linked list matches a downward path. This approach is simple to implement and runs in O(N*M) time where N is the number of tree nodes and M is the linked list length.
Is Linked List in Binary Tree asked at Google/Amazon/Meta?
Binary tree and DFS pattern problems like this frequently appear in interviews at companies such as Amazon, Meta, and Google. The problem tests recursive thinking, tree traversal, and the ability to coordinate two data structures during search.
What data structure is used in Linked List in Binary Tree?
The solution primarily uses binary trees and singly linked lists along with a Depth-First Search traversal strategy. Recursion or an explicit stack is used to explore tree nodes and attempt sequential matching with linked list nodes.
What is the time complexity of Linked List in Binary Tree?
The worst-case time complexity is O(N*M). For every node in the binary tree, the algorithm may attempt to match the entire linked list path. Space complexity is O(H), where H is the height of the binary tree due to recursion or stack usage.

Ready to solve this problem?

Practice Linked List in Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Remove Nth Node From End of List