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.

Description Hints 1 Solution Video 20:58

1367. Linked List in Binary Tree

Medium52.1% acceptance5 companies

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.

Asked at 5 companies

Soundhound

Google Amazon Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Create recursive function, given a pointer in a Linked List and any node in the Binary Tree. Check if all the elements in the linked list starting from the head correspond to some downward path in the binary tree.

20:58

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, val=0, next=None):
4#         self.val = val
5#         self.next = next
6# Definition for a binary tree node.
7# class TreeNode:
8#     def __init__(self, val=0, left=None, right=None):
9#         self.val = val
10#         self.left = left
11#         self.right = right
12class Solution:
13    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
14        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[4,2,8]
[1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]

Input

[1,4,2,6]
[1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]

Input

[1,4,2,6,8]
[1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]

Your code is saved on this device.Solution