1367. Linked List in Binary Tree

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:

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

class Solution {
public:
    bool isSubPath(ListNode* linkedListHead, TreeNode* treeRoot) {
        if (treeRoot == nullptr)
            return false;
        return hasPathStartingFromNode(linkedListHead, treeRoot) ||
               isSubPath(linkedListHead, treeRoot->left) ||
               isSubPath(linkedListHead, treeRoot->right);
    }

private:
    bool hasPathStartingFromNode(ListNode* currentListNode, TreeNode* currentTreeNode) {
        if (currentListNode == nullptr)
            return true;
        if (currentTreeNode == nullptr)
            return false;
        return currentListNode->val == currentTreeNode->val && (hasPathStartingFromNode(currentListNode->next, currentTreeNode->left) || hasPathStartingFromNode(currentListNode->next, currentTreeNode->right));
    }
};

class Solution:
    def isSubPath(self, linkedListHead: Optional[ListNode], treeRoot: Optional[TreeNode]) -> bool:
        if treeRoot is None:
            return False
        return self.hasPathStartingFromNode(linkedListHead, treeRoot) or self.isSubPath(linkedListHead, treeRoot.left) or  self.isSubPath(linkedListHead, treeRoot.right)

    def hasPathStartingFromNode(self, currentListNode: Optional[ListNode], currentTreeNode: Optional[TreeNode]) -> bool:
        if currentListNode is None:
            return True
        if currentTreeNode is None:
            return False
        return currentListNode.val == currentTreeNode.val and  (self.hasPathStartingFromNode(currentListNode.next, currentTreeNode.left) or self.hasPathStartingFromNode(currentListNode.next, currentTreeNode.right))

Time Complexity

• Main Function isSubPath:

  The function isSubPath recursively traverses the entire binary tree to check if any path starting from any node matches the linked list. In the worst case, it will check every node in the tree, leading to a time complexity of \( O(n) \), where n is the total number of nodes in the binary tree.

• Helper Function hasPathStartingFromNode:

  For each node of the tree, the helper function hasPathStartingFromNode checks for the presence of the linked list path starting from that node. In the worst case, this function can go through all nodes of the linked list for each tree node, leading to a time complexity of \( O(m) \), where m is the length of the linked list.

• Overall Time Complexity:

  Combining both parts, the overall time complexity is \( O(n \cdot m) \), where n is the number of nodes in the binary tree and m is the length of the linked list.

Space Complexity

• Auxiliary Space (Recursion):

  The space complexity is determined by the recursion stack. The depth of the recursion stack can go up to the height of the binary tree in the worst case, which is \( O(h) \), where h is the height of the binary tree.

  Additionally, for each call to hasPathStartingFromNode, there can be a recursion depth up to the length of the linked list m. Thus, the auxiliary space complexity could be \( O(h + m) \).

• Overall Space Complexity:

  The overall space complexity is \( O(h + m) \), where h is the height of the binary tree and m is the length of the linked list.