How do you solve Linked List in Binary Tree on LeetCode?

Linked List in Binary Tree (LeetCode #1367) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The problem requires checking paths in a tree structure, which can often be solved with depth-first search.

What is the brute force solution for Linked List in Binary Tree?

The brute force approach for Linked List in Binary Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. We will check every node in the binary tree to see if it matches the head of the linked list. If it does, we will then check if the subsequent nodes in the linked list match the downward path in the binary tree. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Linked List in Binary Tree?

Linked List in Binary Tree uses the following concepts: Linked List, Tree, Depth-First Search, Binary Tree. The recommended patterns to study are: Depth-First Search, Recursion.

What are the interview tips for Linked List in Binary Tree?

Always clarify the problem statement and constraints with the interviewer. Think aloud while coding to show your thought process. Consider edge cases and test your solution with them.

What are common mistakes when solving Linked List in Binary Tree?

Not considering all paths from the binary tree's nodes. Forgetting to handle edge cases like null nodes.

#1367

Linked List in Binary Tree

Medium

Linked ListTreeDepth-First SearchBinary TreeDepth-First SearchRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

We can optimize our approach by using a depth-first search (DFS) that checks for a match with the linked list as we traverse the binary tree. This way, we only traverse the tree once, making our solution more efficient.

⚙️

Algorithm

4 steps

1Step 1: Perform a DFS traversal of the binary tree.
2Step 2: At each node, check if the current node's value matches the head of the linked list.
3Step 3: If it matches, continue checking the next node in the linked list against the left and right children of the current node.
4Step 4: If the linked list is fully matched, return True; otherwise, backtrack and continue searching.

solution.py23 lines

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next
5
6class TreeNode:
7    def __init__(self, val=0, left=None, right=None):
8        self.val = val
9        self.left = left
10        self.right = right
11
12class Solution:
13    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
14        if not root:
15            return False
16        return self.dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)
17
18    def dfs(self, head: ListNode, node: TreeNode) -> bool:
19        if not head:
20            return True
21        if not node or node.val != head.val:
22            return False
23        return self.dfs(head.next, node.left) or self.dfs(head.next, node.right)

ℹ

Complexity note: The time complexity is O(n) because we traverse each node in the binary tree once. The space complexity is O(n) due to the recursion stack in the worst case.

1The problem requires checking paths in a tree structure, which can often be solved with depth-first search.
2Recursive functions can simplify the traversal and matching process.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.