Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Linked List in Binary Tree solution and explanation

MediumBinary TreeDepth-First SearchLinked ListTree7 min read52.1% acceptanceUpdated 9 Apr 2026
Asked atSoundhoundGoogleAmazonMetaBloomberg
Practise Linked List in Binary Tree
20:58
Linked List in Binary Tree | Easy | Dry Run | Leetcode 1367 | codestorywithMIKcodestorywithMIK · 20:58 · 11K viewsWatch on YouTube
9 more videos on this problem
  1. Linked List in Binary Tree | Easy | Dry Run | Leetcode 1367 | codestorywithMIKcodestorywithMIK · 20:58 · 11K views
  2. Linked List in Binary Tree - Leetcode 1367 - PythonNeetCodeIO · 10:14 · 10K views
  3. LeetCode 1367 - Linked List in Binary TreeLight Of Truth · 8:38 · 319 views
  4. Leetcode-1367 :Linked List in Binary Tree ( Recursive and iterative solution/event trigger pattern )Kumar Sanjeev · 5:16 · 155 views
  5. LeetCode 1367 - Linked List in Binary Tree - JavaAlpha-Code · 14:02 · 141 views
  6. LeetCode 1367 Linked List In Binary Tree | Python Solution #python #leetcode #1367AI Learning Corner · 9:35 · 133 views
  7. Linked List in Binary Tree - Leetcode 1367 - JavaCode With K5KC · 7:38 · 97 views
  8. 1367 Linked List in Binary Tree - Leetcode in Go - Binary tree - Linked listXavier Xie · 9:45 · 89 views
  9. 1367. Linked List in Binary Tree (LeetCode Depth-First Search)Z41N · 6:21 · 50 views
  10. 1367: Linked List in Binary Tree || Leetcode || Linked List || Binary TreeCoding Guys · 19:06 · 43 views

The problem

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.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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: ListNode, root: TreeNode) -> bool:
        if not root:
            return False
        return self.dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)
    
    def dfs(self, head: ListNode, root: TreeNode) -> bool:
        if not head:
            return True
        if not root:
            return False
        if head.val != root.val:
            return False
        return self.dfs(head.next, root.left) or self.dfs(head.next, root.right)
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if (root == null) return false;
        return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }
    
    private boolean dfs(ListNode head, TreeNode root) {
        if (head == null) return true;
        if (root == null) return false;
        if (head.val != root.val) return false;
        return dfs(head.next, root.left) || dfs(head.next, root.right);
    }
}
#include <cstddef>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        if (!root) return false;
        return dfs(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);
    }
    
    bool dfs(ListNode* head, TreeNode* root) {
        if (!head) return true;
        if (!root) return false;
        if (head->val != root->val) return false;
        return dfs(head->next, root->left) || dfs(head->next, root->right);
    }
};
function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function isSubPath(head, root) {
    if (!root) return false;
    return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
}

function dfs(head, root) {
    if (!head) return true;
    if (!root) return false;
    if (head.val !== root.val) return false;
    return dfs(head.next, root.left) || dfs(head.next, root.right);
}
#include <stdbool.h>
#include <stddef.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

bool isSubPathFromNode(struct ListNode* head, struct TreeNode* root) {
    if (!head) return true;
    if (!root) return false;
    if (head->val != root->val) return false;
    return isSubPathFromNode(head->next, root->left) || isSubPathFromNode(head->next, root->right);
}

bool isSubPath(struct ListNode* head, struct TreeNode* root) {
    if (!root) return false;
    if (isSubPathFromNode(head, root)) return true;
    return isSubPath(head, root->left) || isSubPath(head, root->right);
}
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; next = null; }
}

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public bool IsSubPath(ListNode head, TreeNode root) {
        if (root == null) return false;
        return DFS(head, root) || IsSubPath(head, root.left) || IsSubPath(head, root.right);
    }
    
    private bool DFS(ListNode head, TreeNode root) {
        if (head == null) return true;
        if (root == null) return false;
        if (head.val != root.val) return false;
        return DFS(head.next, root.left) || DFS(head.next, root.right);
    }
}

The Python version of the solution uses recursive DFS. The function isSubPath determines starting points for matching the linked list's path in the tree using the helper method dfs.

Complexity

Time Complexity: O(n * m), Space Complexity: O(h), where n, m are the sizes of the tree and list while h is the tree's height.

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.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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: ListNode, root: TreeNode) -> bool:
        stack = [(root, head)]
        while stack:
            node, list_node = stack.pop()
            if not list_node:
                return True
            if not node:
                continue
            if node.val == list_node.val:
                stack.append((node.left, list_node.next))
                stack.append((node.right, list_node.next))
            if list_node.next:
                stack.append((node.left, list_node))
                stack.append((node.right, list_node))
        return False
import java.util.Stack;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        Stack<Pair<TreeNode, ListNode>> stack = new Stack<>();
        stack.push(new Pair<>(root, head));
        
        while (!stack.isEmpty()) {
            Pair<TreeNode, ListNode> curr = stack.pop();
            TreeNode treeNode = curr.getKey();
            ListNode listNode = curr.getValue();

            if (listNode == null) return true;
            if (treeNode == null) continue;
            if (treeNode.val == listNode.val) {
                stack.push(new Pair<>(treeNode.left, listNode.next));  
                stack.push(new Pair<>(treeNode.right, listNode.next));
            }
            if (listNode.next != null) {
                stack.push(new Pair<>(treeNode.left, listNode));
                stack.push(new Pair<>(treeNode.right, listNode));
            }
        }
        return false;
    }
}

// Pair class equivalent to javafx.util.Pair
class Pair<K, V> {
    private K key;
    private V value;

    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }
}
#include <stack>
#include <cstddef>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        std::stack<std::pair<TreeNode*, ListNode*>> s;
        s.emplace(root, head);
        
        while (!s.empty()) {
            auto [treeNode, listNode] = s.top(); s.pop();
            if (!listNode) return true;
            if (!treeNode) continue;
            if (treeNode->val == listNode->val) {
                s.emplace(treeNode->left, listNode->next);  
                s.emplace(treeNode->right, listNode->next);
            }
            if (listNode->next) {
                s.emplace(treeNode->left, listNode);
                s.emplace(treeNode->right, listNode);
            }
        }
        return false;
    }
};
function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function isSubPath(head, root) {
    const stack = [[root, head]];
    while (stack.length > 0) {
        const [node, listNode] = stack.pop();
        if (!listNode) return true;
        if (!node) continue;
        if (node.val === listNode.val) {
            stack.push([node.left, listNode.next]);
            stack.push([node.right, listNode.next]);
        }
        if (listNode.next) {
            stack.push([node.left, listNode]);
            stack.push([node.right, listNode]);
        }
    }
    return false;
}
#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

typedef struct {
    struct TreeNode* node;
    struct ListNode* list;
} StackNode;

bool isSubPath(struct ListNode* head, struct TreeNode* root) {
    if (!root) return false;
    StackNode stack[2500]; // A simple static stack implementation
    int top = -1;
    stack[++top] = (StackNode){root, head};
    
    while (top != -1) {
        StackNode currentNode = stack[top--];
        struct TreeNode* treeNode = currentNode.node;
        struct ListNode* listNode = currentNode.list;

        // Process
        if (!listNode) return true;
        if (!treeNode) continue;
        if (treeNode->val == listNode->val) {
            if (listNode->next == NULL) return true;
            stack[++top] = (StackNode){treeNode->left, listNode->next};
            stack[++top] = (StackNode){treeNode->right, listNode->next};
        }

        // Push next states
        stack[++top] = (StackNode){treeNode->left, listNode};
        stack[++top] = (StackNode){treeNode->right, listNode};
    }

    return false;
}
using System.Collections.Generic;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; next = null; }
}

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public bool IsSubPath(ListNode head, TreeNode root) {
        var stack = new Stack<(TreeNode, ListNode)>();
        stack.Push((root, head));

        while (stack.Count > 0) {
            var (treeNode, listNode) = stack.Pop();
            if (listNode == null) return true;
            if (treeNode == null) continue;
            if (treeNode.val == listNode.val) {
                stack.Push((treeNode.left, listNode.next));
                stack.Push((treeNode.right, listNode.next));
            }
            if (listNode.next != null) {
                stack.Push((treeNode.left, listNode));
                stack.Push((treeNode.right, listNode));
            }
        }
        return false;
    }
}

Python solution also adopts an iterative DFS strategy via stack. It uses list of tuples to track the current tree node and linked list node, processing each by stack operations to expand the search iteratively.

Complexity

Time Complexity: O(n * m), Space Complexity: O(n), with n nodes for the tree and m nodes for the list primarily affecting performance through 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.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

const dfs = (head: ListNode | null, root: TreeNode | null) => {
    if (head == null) {
        return true;
    }
    if (root == null || head.val !== root.val) {
        return false;
    }
    return dfs(head.next, root.left) || dfs(head.next, root.right);
};

function isSubPath(head: ListNode | null, root: TreeNode | null): boolean {
    if (root == null) {
        return false;
    }
    return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
}
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubPath(head *ListNode, root *TreeNode) bool {
	if root == nil {
		return false
	}
	return dfs(head, root) || isSubPath(head, root.Left) || isSubPath(head, root.Right)
}

func dfs(head *ListNode, root *TreeNode) bool {
	if head == nil {
		return true
	}
	if root == nil || head.Val != root.Val {
		return false
	}
	return dfs(head.Next, root.Left) || dfs(head.Next, root.Right)
}
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    fn dfs(head: &Option<Box<ListNode>>, root: &Option<Rc<RefCell<TreeNode>>>) -> bool {
        if head.is_none() {
            return true;
        }
        if root.is_none() {
            return false;
        }
        let node = head.as_ref().unwrap();
        let root = root.as_ref().unwrap().borrow();
        if node.val != root.val {
            return false;
        }
        Self::dfs(&node.next, &root.left) || Self::dfs(&node.next, &root.right)
    }

    fn my_is_sub_path(head: &Option<Box<ListNode>>, root: &Option<Rc<RefCell<TreeNode>>>) -> bool {
        if root.is_none() {
            return false;
        }
        let node = root.as_ref().unwrap().borrow();
        Self::dfs(head, root)
            || Self::my_is_sub_path(head, &node.left)
            || Self::my_is_sub_path(head, &node.right)
    }

    pub fn is_sub_path(head: Option<Box<ListNode>>, root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        Self::my_is_sub_path(&head, &root)
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Recursive Depth-First Search

Time Complexity: O(n * m), Space Complexity: O(h), where n, m are the sizes of the tree and list while h is the tree's height.

Iterative Depth-First Search with Stack

Time Complexity: O(n * m), Space Complexity: O(n), with n nodes for the tree and m nodes for the list primarily affecting performance through stack usage.

Recursion–

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.

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.

Comments

Now write it yourselfClose this page and solve Linked List in Binary Tree in the editor, without looking.
Practise Linked List in Binary Tree