Linked List in Binary Tree

Leetcode Problem:

• Linked List in Binary Tree

Summary

• Check if all elements in a linked list are present in a binary tree

Approach

• This solution first traverses the linked list and stores its elements in a vector
• Then it creates a hash table to store the indices of the elements in the vector
• It then checks if the binary tree contains all the elements of the linked list by traversing the tree and using the hash table to keep track of the current position in the linked list.

Complexity

• O(n*m) where n is the number of nodes in the binary tree and m is the number of nodes in the linked list

Explain

• The solution works by first storing the elements of the linked list in a vector
• It then creates a hash table to store the indices of the elements in the vector
• This is done by iterating over the vector and storing the index of each element in the hash table
• The hash table is used to keep track of the current position in the linked list when traversing the binary tree
• If the binary tree contains all the elements of the linked list, the solution returns true
• Otherwise, it returns false.

Solution Code:

/**
 * 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:
    vector listNode;
    int pi[100];
    int match;
    bool traversal(TreeNode* root, int match){
        if (match == listNode.size()) return true;
        if(root == nullptr) return false;
        while(match != 0 && root->val != listNode[match]){
            match = pi[match -1];
        }
        if(root->val == listNode[match]){
            match++;
        }
        if (traversal(root->left, match)){
            return true;
        }
        if (traversal(root->right, match)){
            return true;
        }
        return false;
    }
    bool isSubPath(ListNode* head, TreeNode* root) {
        while(head){
            listNode.push_back(head->val);
            head = head->next;
        }
        match = 0;
        for(int i = 1; i < listNode.size(); i++){
            while(match != 0 && listNode[i] != listNode[match]){
                match = pi[match-1];
            }
            if(listNode[i] == listNode[match]){
                match++;
            }
            pi[i] = match;
        }
        if (traversal(root, 0)){
            return true;
        }
        return false;
    }
};