# Linked List in Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/linked-list-in-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/linked-list-in-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Linked List, Tree, Binary Tree
**Companies:** [SoundHound](https://scaleengineer.com/companies/soundhound)
---
## 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:**

**![](https://assets.glich.co/dsa/linked-list-in-binary-tree/image0.png)**

**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:**

**![](https://assets.glich.co/dsa/linked-list-in-binary-tree/image1.png)**

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

# Approaches
## Brute Force: Double Recursion
This approach involves traversing every node of the binary tree. For each node, we perform a separate check to see if a downward path starting from that node matches the entire linked list. This is straightforward but can be inefficient as it may re-check the same subpaths multiple times.
**Time:** O(N * L), where N is the number of nodes in the tree and L is the length of the linked list. In the worst case, for each of the N tree nodes, we might traverse L nodes deep to check for a path match. · **Space:** O(H), where H is the height of the tree. This is due to the recursion stack depth. In the worst-case scenario of a skewed tree, H can be equal to N, making the space complexity O(N).
**Pros:** Simple to understand and implement.; Uses a standard recursive pattern for tree problems.
**Cons:** Inefficient due to repeated computations. The `dfs` helper might be called on the same nodes multiple times for different starting points.; Can lead to a 'Time Limit Exceeded' error on large test cases.
### Explanation
We define two recursive functions.

The main function, `isSubPath(head, root)`, traverses the entire tree. Its purpose is to find a starting node in the tree that matches the head of the linked list.
- It checks three conditions:
  1. Does a path starting from the current `root` match the list? (This is checked by a helper function).
  2. If not, does a matching path exist in the left subtree? (Recursive call: `isSubPath(head, root.left)`).
  3. If not, does a matching path exist in the right subtree? (Recursive call: `isSubPath(head, root.right)`).
- If any of these are true, we've found a match.

The helper function, `dfs(listNode, treeNode)`, checks if a path starting from `treeNode` matches the list starting from `listNode`.
- Base Case 1: If `listNode` is null, it means we've successfully matched all elements of the list. Return `true`.
- Base Case 2: If `treeNode` is null or the values don't match (`treeNode.val != listNode.val`), the path is broken. Return `false`.
- Recursive Step: If the current nodes match, we continue the search downwards. We check if the rest of the list (`listNode.next`) matches a path starting from either the left child (`treeNode.left`) or the right child (`treeNode.right`). Return `dfs(listNode.next, treeNode.left) || dfs(listNode.next, treeNode.right)`.

The initial call is `isSubPath(head, root)`.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if (root == null) {
            return false;
        }
        // Check if a path starts from the current root
        if (dfs(head, root)) {
            return true;
        }
        // If not, check the left and right subtrees
        return isSubPath(head, root.left) || isSubPath(head, root.right);
    }

    // Helper function to check for a matching path from a given tree node
    private boolean dfs(ListNode head, TreeNode root) {
        // Base case: If we've reached the end of the list, we found a match
        if (head == null) {
            return true;
        }
        // Base case: If we've run out of tree nodes or values don't match
        if (root == null || head.val != root.val) {
            return false;
        }
        // Recursive step: Check left and right children for the next list node
        return dfs(head.next, root.left) || dfs(head.next, root.right);
    }
}
```
### Algorithm
- Define a main function `isSubPath(head, root)`.
- If `root` is null, return `false` as no path can be formed.
- Call a helper function `dfs(head, root)` to check if a path matching the list starts at the current `root`.
- If `dfs` returns `true`, we found a match, so return `true`.
- Otherwise, recursively call `isSubPath` on the left and right children: `isSubPath(head, root.left) || isSubPath(head, root.right)`.
- The helper function `dfs(listNode, treeNode)` works as follows:
- If `listNode` is null, return `true` (end of list reached).
- If `treeNode` is null or `listNode.val != treeNode.val`, return `false` (path broken).
- Return the result of checking the next list node against the left and right children: `dfs(listNode.next, treeNode.left) || dfs(listNode.next, treeNode.right)`.

## Optimized DFS with KMP Algorithm
This approach improves upon the brute-force method by using the Knuth-Morris-Pratt (KMP) string searching algorithm. The KMP algorithm is known for its efficiency in finding a pattern within a text by pre-processing the pattern to avoid redundant comparisons. Here, the linked list is our 'pattern' and the paths in the tree are our 'text'. We traverse the tree only once, using the KMP's state-machine-like logic to track the matching progress.
**Time:** O(N + L), where N is the number of nodes in the tree and L is the length of the list. Converting the list to an array and building the LPS array takes O(L). The DFS traversal visits each tree node once. The KMP logic at each node has an amortized constant time complexity, leading to an O(N) traversal. Thus, the total time is O(N + L). · **Space:** O(L + H), where L is the list length and H is the tree height. We need O(L) space for the pattern array and the LPS array. The recursion stack for DFS requires O(H) space. In the worst case, H can be N, making the space O(L + N).
**Pros:** Highly efficient with linear time complexity.; Avoids redundant comparisons by intelligently reusing information from previous partial matches.
**Cons:** More complex to understand and implement compared to the brute-force approach.; Requires knowledge of the KMP algorithm.
### Explanation
The core idea is to avoid restarting the search from scratch when a mismatch occurs. The KMP algorithm uses a precomputed 'Longest Proper Prefix which is also a Suffix' (LPS) array to know where to resume matching.

**Step 1: Pre-processing**
- Convert the linked list into an integer array, let's call it `pattern`. This makes random access possible.
- Compute the LPS array for the `pattern`. The `lps[i]` value stores the length of the longest proper prefix of `pattern[0...i]` that is also a suffix of `pattern[0...i]`. This step takes O(L) time.

**Step 2: KMP-style DFS Traversal**
- We perform a single Depth-First Search (DFS) on the tree. The DFS function will take the current `treeNode` and the current length of the matched prefix, `j`, as parameters: `kmpDfs(treeNode, j)`.
- Inside `kmpDfs(treeNode, j)`:
  - If a full match has already been found, we can stop early (optional optimization).
  - Using the KMP logic, we find the new match length. While `j > 0` and the current `treeNode.val` does not match `pattern[j]`, we 'fall back' by setting `j = lps[j-1]`. This efficiently finds the next best partial match.
  - If `treeNode.val` matches `pattern[j]`, we extend our match by incrementing `j`.
  - If `j` becomes equal to the length of the pattern (L), we have found a complete match. We can set a global flag to `true` and return.
  - Recursively call `kmpDfs` for the left and right children, passing the updated match length `j`.

The initial call is `kmpDfs(root, 0)`.

```java
class Solution {
    private boolean found = false;

    public boolean isSubPath(ListNode head, TreeNode root) {
        if (head == null) return true;
        if (root == null) return false;

        // 1. Convert linked list to an array (pattern)
        java.util.List<Integer> patternList = new java.util.ArrayList<>();
        ListNode current = head;
        while (current != null) {
            patternList.add(current.val);
            current = current.next;
        }
        int[] pattern = patternList.stream().mapToInt(i -> i).toArray();
        
        // 2. Compute the KMP (LPS) array
        int[] lps = computeLPS(pattern);

        // 3. Perform DFS with KMP logic
        dfs(root, 0, pattern, lps);
        return found;
    }

    private void dfs(TreeNode node, int j, int[] pattern, int[] lps) {
        if (node == null || found) {
            return;
        }

        // KMP match logic
        while (j > 0 && node.val != pattern[j]) {
            j = lps[j - 1];
        }
        if (node.val == pattern[j]) {
            j++;
        }

        // Check if pattern is fully matched
        if (j == pattern.length) {
            found = true;
            return;
        }

        // Recurse on children
        dfs(node.left, j, pattern, lps);
        dfs(node.right, j, pattern, lps);
    }

    private int[] computeLPS(int[] pattern) {
        int m = pattern.length;
        int[] lps = new int[m];
        int length = 0; // length of the previous longest prefix suffix
        int i = 1;

        while (i < m) {
            if (pattern[i] == pattern[length]) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
}
```
### Algorithm
- Convert the linked list into an integer array `pattern` of length `L`.
- Compute the KMP Longest Proper Prefix Suffix (LPS) array for `pattern`. This takes O(L) time.
- Define a DFS function `dfs(node, j, pattern, lps)` where `j` is the current length of the matched prefix.
- Inside `dfs`, if `node` is null or a match has already been found, return.
- Apply the KMP matching logic: while `j > 0` and `node.val != pattern[j]`, update `j` to `lps[j-1]`.
- If `node.val == pattern[j]`, increment `j`.
- If `j` equals the pattern length `L`, a full match is found. Set a flag to `true` and return.
- Recursively call `dfs` for the left and right children with the new value of `j`.
- Initiate the process by calling `dfs(root, 0, pattern, lps)`.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ 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 || head . val != root . val ) { return false ; } return dfs ( head . next , root . left ) || dfs ( head . next , root . right ); } }
```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ 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 || head -> val != root -> val ) { return false ; } return dfs ( head -> next , root -> left ) || dfs ( head -> next , root -> right ); } };
```

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next # Definition for a binary tree node. # 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 : Optional [ ListNode ], root : Optional [ TreeNode ]) -> bool : def dfs ( head , root ): if head is None : return True if root is None or root . val != head . val : return False return dfs ( head . next , root . left ) or dfs ( head . next , root . right ) if root is None : return False return ( dfs ( head , root ) or self . isSubPath ( head , root . left ) or self . isSubPath ( head , root . right ) )
```