Linked List in Binary Tree

Problem Statement

The task involves determining if a linked list can be represented as a downward path in a given binary tree. A downward path is defined as a sequence that begins at any node in the binary tree and progresses downwards. For the linked list to correspond to a downward path within the binary tree, each element, starting from the head of the list, must sequentially match the values of the nodes along this path in the tree.

Examples

Example 1

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

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.

Approach and Intuition

To tackle this problem, a systematic approach needs to be followed by considering how the linked list could fit into the binary tree's structure:

1. Begin at the root node of the binary tree and try to find a node that has the same value as the head of the linked list.
2. From this starting node, traverse through the binary tree by following the linked list. For each node in the binary tree:
   • Compare the current binary tree node's value with the current linked list node's value.
   • If the values match, move to the next node in both the linked list and the binary tree (children of the current binary tree node).
   • If at any point values do not match or the linked list is not exhausted after reaching a leaf node in the tree, backtrack and explore a different path from the same starting node.
3. If no starting node in the binary tree matches the head of the linked list, or if a complete match for the entire list is not found in any downward path from these starting positions, return false. Otherwise, if a complete path correspondence is found, return true.

This problem effectively reduces to recursively scanning each potential starting node in the binary tree and attempting to map each subsequent node in the linked list to a downward path originating from this candidate node. This solution requires both backtracking for exploring different potential starts and deep traversal to ensure the entire linked list can be mapped to nodes in the tree over potential paths.

Solutions

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);
    }
};