Linked List In Binary Tree - Leetcode Solution

Problem: 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.

Notice that the respective levels in the binary tree where elements of the linked list are matched must have the same height.

Example 1:

Input:

head: 1->2->3

root: [1,2,3,4,5,6,7]

Output: true

Explanation:

The nodes in the linked list correspond to the path 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

Example 2:

Input:

head: 1->2->3

root: [1,2,3,null,4,5,6]

Output: false

Explanation:

The nodes in the linked list correspond to the path 1 -> 2 -> 3 -> 6 -> 7, which is not connected to any path in the binary tree.

Constraints:

1 <= node.val <= 100 for each node in the linked list and binary tree.

The given linked list and binary tree will contain between 1 and 100 nodes.

Solution:

This problem can be solved by using recursion and two helper functions.

The first helper function "check" takes in the current node in the binary tree and the current node in the linked list and checks if the elements in the linked list starting from the current node correspond to a downward path connected in the binary tree.

The second helper function "traverse" takes in the current node in the binary tree and the head node of the linked list and recursively checks if there exists a path starting from the current node in the binary tree that corresponds to the linked list.

If the current node in the binary tree is null, we return false because we have reached the end of the binary tree and there is no path in the binary tree that corresponds to the linked list.

If the current node in the binary tree matches the head node of the linked list, we call the "check" function to check if the elements in the linked list starting from the current node correspond to a downward path connected in the binary tree. If the "check" function returns true, we return true.

If none of the above cases are true, we recursively call the "traverse" function for the left and right children of the current node in the binary tree.

Pseudocode:

check(current_node, current_linked_list_node): if current_node is null or current_linked_list_node is null: return true if current_node.val != current_linked_list_node.val: return false return check(current_node.left, current_linked_list_node.next) or check(current_node.right, current_linked_list_node.next)

traverse(current_node, head): if current_node is null: return false if current_node.val == head.val: if check(current_node, head): return true return traverse(current_node.left, head) or traverse(current_node.right, head)

main(root, head): return traverse(root, head)

Time Complexity:

The time complexity of this solution is 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. The worst-case scenario is when each node in the binary tree is checked against each node in the linked list.

Space Complexity:

The space complexity of this solution is O(h) where h is the height of the binary tree. The space complexity is the maximum stack space used by the recursive calls to traverse the binary tree.

1