Linked List in Binary Tree

• 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).

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

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11/**12 * Definition for a binary tree node.13 * public class TreeNode {14 *     int val;15 *     TreeNode left;16 *     TreeNode right;17 *     TreeNode() {}18 *     TreeNode(int val) { this.val = val; }19 *     TreeNode(int val, TreeNode left, TreeNode right) {20 *         this.val = val;21 *         this.left = left;22 *         this.right = right;23 *     }24 * }25 */26class Solution {27    public boolean isSubPath(ListNode head, TreeNode root) {28        if (root == null) {29            return false;30        }31        // Check if a path starts from the current root32        if (dfs(head, root)) {33            return true;34        }35        // If not, check the left and right subtrees36        return isSubPath(head, root.left) || isSubPath(head, root.right);37    }38 39    // Helper function to check for a matching path from a given tree node40    private boolean dfs(ListNode head, TreeNode root) {41        // Base case: If we've reached the end of the list, we found a match42        if (head == null) {43            return true;44        }45        // Base case: If we've run out of tree nodes or values don't match46        if (root == null || head.val != root.val) {47            return false;48        }49        // Recursive step: Check left and right children for the next list node50        return dfs(head.next, root.left) || dfs(head.next, root.right);51    }52}

• 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).

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

1class Solution {2    private boolean found = false;3 4    public boolean isSubPath(ListNode head, TreeNode root) {5        if (head == null) return true;6        if (root == null) return false;7 8        // 1. Convert linked list to an array (pattern)9        java.util.List<Integer> patternList = new java.util.ArrayList<>();10        ListNode current = head;11        while (current != null) {12            patternList.add(current.val);13            current = current.next;14        }15        int[] pattern = patternList.stream().mapToInt(i -> i).toArray();16        17        // 2. Compute the KMP (LPS) array18        int[] lps = computeLPS(pattern);19 20        // 3. Perform DFS with KMP logic21        dfs(root, 0, pattern, lps);22        return found;23    }24 25    private void dfs(TreeNode node, int j, int[] pattern, int[] lps) {26        if (node == null || found) {27            return;28        }29 30        // KMP match logic31        while (j > 0 && node.val != pattern[j]) {32            j = lps[j - 1];33        }34        if (node.val == pattern[j]) {35            j++;36        }37 38        // Check if pattern is fully matched39        if (j == pattern.length) {40            found = true;41            return;42        }43 44        // Recurse on children45        dfs(node.left, j, pattern, lps);46        dfs(node.right, j, pattern, lps);47    }48 49    private int[] computeLPS(int[] pattern) {50        int m = pattern.length;51        int[] lps = new int[m];52        int length = 0; // length of the previous longest prefix suffix53        int i = 1;54 55        while (i < m) {56            if (pattern[i] == pattern[length]) {57                length++;58                lps[i] = length;59                i++;60            } else {61                if (length != 0) {62                    length = lps[length - 1];63                } else {64                    lps[i] = 0;65                    i++;66                }67            }68        }69        return lps;70    }71}