Leetcode 1367: Linked List in Binary Tree

Input: The input consists of a linked list and a binary tree. The linked list is represented as an array of values and the binary tree is represented as a root node of a binary tree structure.

Example: head = [4, 2, 8], root = [1, 4, 4, null, 2, 2, null, 1, null, 6, 8, null, null, null, null, 1, 3]

Constraints:

• The number of nodes in the binary tree will be in the range [1, 2500].

• The number of nodes in the linked list will be in the range [1, 100].

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

Output: Return True if there exists a downward path in the binary tree that matches all elements of the linked list starting from its head node, otherwise return False.

Example: True

Constraints:

• The result will be a boolean value: True or False.

Goal: To determine if there exists a downward path in the binary tree that matches all elements of the linked list starting from the head node.

Steps:

• Perform a depth-first search (DFS) to check if the current node value matches the head of the linked list.

• If a match is found, recursively check the left and right child nodes to see if the subsequent linked list elements match the downward path.

• If no match is found at any step, return False.

Goal: Ensure the solution efficiently handles large inputs and follows the problem constraints.

Steps:

• The binary tree has at most 2500 nodes.

• The linked list has at most 100 nodes.

Assumptions:

• The binary tree and linked list contain valid values as per the problem constraints.

• The input tree and linked list are not null.

• Input: head = [4, 2, 8], root = [1, 4, 4, null, 2, 2, null, 1, null, 6, 8, null, null, null, null, 1, 3]

• Explanation: The linked list elements [4, 2, 8] correspond to a downward path starting from node 4, then node 2, and then node 8 in the binary tree.

• Input: head = [1, 4, 2, 6], root = [1, 4, 4, null, 2, 2, null, 1, null, 6, 8, null, null, null, null, 1, 3]

• Explanation: The linked list elements [1, 4, 2, 6] form a valid downward path in the binary tree, matching the nodes from root down to 6.

Approach: The approach is to perform a depth-first search (DFS) to check for downward paths in the binary tree that match the linked list values.

Observations:

• A DFS approach can be used to search the binary tree for matching downward paths.

• At each node, check if it matches the current head of the linked list. If so, recursively check the left and right subtrees.

Steps:

• Start from the root of the binary tree and check if the current node's value matches the head of the linked list.

• If the value matches, recursively check both the left and right child nodes to see if the next elements in the linked list match the path.

• If a match is found, return True, otherwise continue the search or return False if no matches are found.

Empty Inputs:

• If the binary tree is empty, return False.

Large Inputs:

• Ensure the solution handles trees with up to 2500 nodes efficiently.

Special Values:

• If there is only one element in the linked list, check if that element exists as a downward path in the tree.

Constraints:

• The solution must efficiently handle the maximum constraints for both tree and list sizes.

bool isSubPath(ListNode* head, TreeNode* root) {
    if(head == NULL) return true;
    if(root == NULL) return false;
    return dfs(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);
}

bool dfs(ListNode* head, TreeNode* root) {
    if(head == NULL) return true;
    if(root == NULL) return false;
    return (head->val == root->val) && (dfs(head->next, root->left) || dfs(head->next, root->right));
}

1 : Function Declaration

bool isSubPath(ListNode* head, TreeNode* root) {

The function 'isSubPath' takes two parameters: a linked list 'head' and a binary tree 'root'. It returns true if a path from the linked list exists in the binary tree.

2 : Base Case for Linked List

    if(head == NULL) return true;

This is a base case where if the linked list 'head' is NULL, it indicates the end of the list has been reached, and thus the path has been successfully matched.

3 : Base Case for Binary Tree

    if(root == NULL) return false;

This is a base case where if the binary tree 'root' is NULL, it means there is no path to follow, so we return false.

4 : Recursive Search

    return dfs(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);

The function recursively checks if the linked list matches starting from the current node in the binary tree or its left or right children.

5 : Function Declaration

bool dfs(ListNode* head, TreeNode* root) {

The function 'dfs' is a helper function that recursively checks whether the linked list starting from 'head' can match the binary tree starting from 'root'.

6 : Base Case for Linked List

    if(head == NULL) return true;

This is a base case where if the linked list 'head' is NULL, it indicates that the linked list has been completely matched.

7 : Base Case for Binary Tree

    if(root == NULL) return false;

This base case checks if the binary tree 'root' is NULL, which means the tree path has ended without matching the linked list.

8 : Recursive Matching

    return (head->val == root->val) && (dfs(head->next, root->left) || dfs(head->next, root->right));

The function compares the current node values of the linked list and the binary tree. If they match, it recursively checks the next node in the list against the left or right children of the current tree node.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: In the worst case, the algorithm must visit every node in the tree.

Best Case: O(h)

Worst Case: O(h)

Description: The space complexity is determined by the height of the binary tree due to recursive calls, where h is the height of the tree.

Leetcode 1367: Linked List in Binary Tree

Explore →