Linked List in Binary Tree

class Solution {
public:
    bool isSubsequence(ListNode* listHead, TreeNode* treeRoot) {
        // Preprocess the linked list to create search pattern
        vector<int> nodeValues = {listHead->val}, jumpTable = {0};
        int nextMatch = 0;
        listHead = listHead->next;

        while (listHead) {
            while (nextMatch && listHead->val != nodeValues[nextMatch])
                nextMatch = jumpTable[nextMatch - 1];
            nextMatch += listHead->val == nodeValues[nextMatch];
            nodeValues.push_back(listHead->val);
            jumpTable.push_back(nextMatch);
            listHead = listHead->next;
        }

        // Use Depth First Search to find the sequence in the binary tree
        return findSequence(treeRoot, 0, nodeValues, jumpTable);
    }

private:
    bool findSequence(TreeNode* treeNode, int currentValueIndex,
                      const vector<int>& nodeValues,
                      const vector<int>& jumpTable) {
        if (!treeNode) return false;
        
        while (currentValueIndex && treeNode->val != nodeValues[currentValueIndex])
            currentValueIndex = jumpTable[currentValueIndex - 1];
        currentValueIndex += treeNode->val == nodeValues[currentValueIndex];

        // Confirm if entire sequence is found
        if (currentValueIndex == nodeValues.size()) return true;

        // Continue search on left and right children
        return findSequence(treeNode->left, currentValueIndex, nodeValues, jumpTable) ||
               findSequence(treeNode->right, currentValueIndex, nodeValues, jumpTable);
    }
};

This C++ solution implements a function to determine if a linked list is a subsequence of the paths in a binary tree. Here’s a breakdown of how the solution is structured and operates:

• A primary function, isSubsequence, preprocesses the linked list by extracting its values into a vector and creating a jump table utilizing the KMP (Knuth-Morris-Pratt) pattern matching algorithm's partial match table. This table helps in efficiently finding subsequences.
• It then performs a depth-first search (DFS) on the binary tree to locate a path that matches the linked list sequence using the preprocessed vector and jump table.
• The secondary function, findSequence, conducts the DFS. It compares each node's value against the expected sequence from the linked list. If a mismatch occurs, the function utilizes the jump table to skip unnecessary comparisons, speeding up the search process.
• The DFS continues recursively through both left and right children of the current node until it either finds the complete sequence, indicating the linked list is a subsequence of a path in the tree, or exhausts all paths without a match.

This method ensures that the algorithm efficiently processes and matches the linked list against all paths in the binary tree, handling the problem with both effectiveness and optimal performance in mind.

class Solution {

    public boolean checkSubPath(ListNode head, TreeNode root) {
        List<Integer> sequence = new ArrayList<>();
        List<Integer> lps = new ArrayList<>();
        sequence.add(head.val);
        lps.add(0);
        int idx = 0;
        head = head.next;
        
        while (head != null) {
            while (idx > 0 && head.val != sequence.get(idx)) {
                idx = lps.get(idx - 1);
            }
            idx += head.val == sequence.get(idx) ? 1 : 0;
            sequence.add(head.val);
            lps.add(idx);
            head = head.next;
        }
        
        return dfsCheck(root, 0, sequence, lps);
    }

    private boolean dfsCheck(
        TreeNode node,
        int idx,
        List<Integer> sequence,
        List<Integer> lps
    ) {
        if (node == null) return false;

        while (idx > 0 && node.val != sequence.get(idx)) {
            idx = lps.get(idx - 1);
        }
        idx += node.val == sequence.get(idx) ? 1 : 0;
        
        if (idx == sequence.size()) return true;

        return dfsCheck(node.left, idx, sequence, lps) || dfsCheck(node.right, idx, sequence, lps);
    }
}

The solution provided consists of a Java class named Solution that checks if a linked list is a subpath within a binary tree. The class implements a method checkSubPath which accepts the head of the linked list and the root of the binary tree as parameters.

• The checkSubPath method first constructs a list of integers (sequence) from the linked list and calculates the Longest Prefix Suffix (LPS) array (lps) for KMP algorithm application.
• For each node in the binary tree, the method then recursively checks (using dfsCheck) if there exists a path starting from this node that matches the sequence derived from the linked list using depth-first search approach.

Key components of the implementation:

• Sequence and LPS Array Construction:

  • Converts the linked list into an array of values (sequence).
  • Builds an array (lps) that represents the longest prefix which is also a suffix for each prefix of the array.

• Depth-First Search (DFS) Check:

  • The dfsCheck private method recursively explores each node of the binary tree to match the sequence using the LPS array for efficient mismatch handling.
  • It simultaneously traverses the binary tree and checks sequence match, adjusting the position based on LPS in case of mismatches.

• Base and Recursive Cases:

  • The base case for recursion is when the current tree node is null, returning false.
  • On a match, the search continues left and right, deepening into the tree structure.
  • If the entire sequence matches at any point, true is returned, indicating a complete match was found.

Performance Consideration: The use of KMP pattern matching principle via the LPS array helps in optimizing the solution by reducing unnecessary comparisons, especially when backtracking on mismatches.

This implementation not only ensures the matching of the linked list sequence within the binary tree paths but does so efficiently by adopting a systematic combination of linear sequence transformation and deep tree traversal strategies.

class Solution:
    def hasSubPath(
        self, list_head: Optional[ListNode], tree_root: Optional[TreeNode]
    ) -> bool:

        # Building the sequence from the linked list values
        sequence = [list_head.val]
        lps = [0]
        seq_idx = 0
        list_head = list_head.next

        while list_head:
            while seq_idx > 0 and list_head.val != sequence[seq_idx]:
                seq_idx = lps[seq_idx - 1]
            if list_head.val == sequence[seq_idx]:
                seq_idx += 1
            sequence.append(list_head.val)
            lps.append(seq_idx)
            list_head = list_head.next

        # Start DFS to find the sequence in binary tree
        return self._dfs_search(tree_root, 0, sequence, lps)

    def _dfs_search(
        self,
        tree_node: Optional[TreeNode],
        seq_idx: int,
        sequence: List[int],
        lps: List[int],
    ) -> bool:
        if not tree_node:
            return False

        while seq_idx > 0 and tree_node.val != sequence[seq_idx]:
            seq_idx = lps[seq_idx - 1]
        if tree_node.val == sequence[seq_idx]:
            seq_idx += 1

        # If entire sequence is found
        if seq_idx == len(sequence):
            return True

        # Recurse left and right
        return self._dfs_search(
            tree_node.left, seq_idx, sequence, lps
        ) or self._dfs_search(
            tree_node.right, seq_idx, sequence, lps
        )

This Python solution tackles the problem of determining whether a linked list exists as a subpath within a binary tree. The approach combines traversal and pattern matching techniques, specifically Depth-First Search (DFS) and the Knuth-Morris-Pratt (KMP) algorithm for sequence matching.

The solution involves two primary components:

1. Sequence Construction from Linked List:

   • Start by extracting the values from the linked list into a sequence list.
   • Use the KMP algorithm's partial match table to optimize the search process, storing the lengths of the longest proper prefix which is also a suffix in the lps list.
   • Iterate through the linked list, updating the sequence and lps list based on the KMP algorithm's criteria.

2. DFS to Find the Sequence in Binary Tree:

   • Implement a recursive _dfs_search function to explore the binary tree.
   • For each node, the function checks if the node's value matches the current index of the sequence using the partial match table from the KMP algorithm to handle mismatches efficiently.
   • If the entire sequence matches at any point during the DFS traversal of the tree, it returns True.
   • If no match is found by the end of the tree traversal, it returns False.

The solution effectively uses the combination of sequence construction from the linked list and subsequent DFS to locate this sequence within the binary tree. This method ensures optimal performance by leveraging the preprocessing step of the KMP algorithm in the sequence matching process within the DFS traversal, minimizing unnecessary comparisons.