Linked List in Binary Tree - Video Solutions

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.