Linked List in Binary Tree

Medium

Oracle

1 view

Topics:

Linked ListsTreesRecursion

You are given a binary tree root and a linked list with head as the first node. Determine whether all the elements in the linked list, starting from the head, correspond to some downward path connected in the binary tree. A downward path means a path that starts at some node and goes downwards (towards the leaves).

Examples:

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 4 -> 2 -> 8 in the binary tree form a subpath matching the linked list.

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

Explanation:

Nodes 1 -> 4 -> 2 -> 6 in the binary tree form a subpath matching the linked list.

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.

Clarifications:

The values in the linked list and binary tree nodes are integers.
The binary tree can be unbalanced.
The function should return true if any downward path in the binary tree matches the linked list.

How would you approach this problem? Consider edge cases such as empty trees or lists, and aim for an efficient solution.

Linked List in Binary Tree

Medium

Oracle

1 view

Topics:

Linked ListsTreesRecursion

You are given a binary tree root and a linked list with head as the first node. Determine whether all the elements in the linked list, starting from the head, correspond to some downward path connected in the binary tree. A downward path means a path that starts at some node and goes downwards (towards the leaves).

Examples:

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 4 -> 2 -> 8 in the binary tree form a subpath matching the linked list.

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

Explanation:

Nodes 1 -> 4 -> 2 -> 6 in the binary tree form a subpath matching the linked list.

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.

Clarifications:

The values in the linked list and binary tree nodes are integers.
The binary tree can be unbalanced.
The function should return true if any downward path in the binary tree matches the linked list.

How would you approach this problem? Consider edge cases such as empty trees or lists, and aim for an efficient solution.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list and binary tree contain duplicate values, and if so, how should I handle them?
What should I return if the linked list is empty, or if the binary tree is empty, or if the linked list is not found within the binary tree?
Are the values in the linked list and binary tree guaranteed to be of a specific data type (e.g., integers), and what is the range of possible values?
Does the linked list have to be matched consecutively as a downward path in the binary tree, or can the linked list nodes appear in any order as long as the values match a path from root to leaf?
If there are multiple occurrences of the linked list in the binary tree, should I return the first one found, or is there a specific one I should prioritize (e.g., the one closest to the root)?

Brute Force Solution

Approach

The brute force method exhaustively explores all potential placements of the linked list within the binary tree. Think of trying to fit a specific jigsaw piece into every possible location of a larger puzzle. If a potential placement matches the linked list's sequence, we have a match.

Here's how the algorithm would work step-by-step:

Begin by examining the root of the binary tree to see if the beginning of the linked list matches it.
If it does, check if the rest of the linked list appears in the tree, following the path down from that root.
If a match is found when checking the path, report that a match exists and terminate.
If the linked list did not appear down that tree, look at the left branch of the tree's root and try to match the start of the linked list there. Repeat the path-following check.
If you still haven't found a match, proceed to the right branch of the root and attempt to match the beginning of the linked list from that point. Also, complete the path-following check there.
Continue this process by inspecting every single node of the binary tree, one by one, to see if the beginning of the linked list matches at any of those nodes.
Each time you find a possible match (i.e., the starting node of the list lines up with a tree node), attempt to trace the remaining linked list in a path downward from that node to confirm whether the entire list exists sequentially in the tree.
If after checking every single node in the tree you cannot find a complete linked list match, then you know that the linked list does not exist as a sequence in the tree.

Code Implementation

def is_linked_list_in_binary_tree(binary_tree_root, linked_list_head):

    def check_from_node(tree_node, list_node):
        if not list_node:
            return True
        if not tree_node:
            return False
        if tree_node.val != list_node.val:
            return False

        return check_from_node(tree_node.left, list_node.next) or \
               check_from_node(tree_node.right, list_node.next)

    def traverse_tree(tree_node, linked_list_head):
        if not linked_list_head:
            return True
        if not tree_node:
            return False

        # Check if linked list matches starting from this node
        if check_from_node(tree_node, linked_list_head):
            return True

        # Recursively check the left and right subtrees
        return traverse_tree(tree_node.left, linked_list_head) or \
               traverse_tree(tree_node.right, linked_list_head)

    # Need to handle empty linked list case
    if not linked_list_head:
        return True

    # Initiate the traversal from the root of the binary tree
    return traverse_tree(binary_tree_root, linked_list_head)

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the number of nodes in the binary tree and m be the number of nodes in the linked list. We iterate through each node in the binary tree, which takes O(n) time. For each node, we attempt to match the linked list starting from that node. Matching the linked list requires traversing at most m nodes of the tree to check if the list exists as a sequence, costing O(m) time. Thus, the total time complexity is O(n * m), where n is the number of tree nodes and m is the number of linked list nodes.

Space Complexity

O(H) – The space complexity is determined by the maximum depth of the recursive calls made during the path-following checks. In the worst-case scenario, the recursion stack grows to the height (H) of the binary tree because the algorithm explores each path from the root to the leaves. Therefore, the auxiliary space used is proportional to the tree's height. In the balanced tree case, H is log(N) where N is the number of nodes in the tree, but in the skewed tree case H could be N. We generally assume the worst case.

Optimal Solution

Approach

The best way to solve this is to first check if the tree contains the first value of the linked list. If it does, we need to check if the linked list exists starting from that node in the tree. We do this recursively by walking through the linked list and the tree simultaneously.

Here's how the algorithm would work step-by-step:

First, if the linked list is empty, we can say that the linked list exists in the tree.
If the tree is empty, but the linked list is not, then we know that the linked list does not exist in the tree.
Now, we recursively go through the tree and check each node of the tree. We need to find the node that has the same value as the first node of the linked list.
Once we find the node in the tree whose value matches the head of the linked list, then we try to find the linked list starting from that node.
In the helper method to check if a linked list exists starting from a tree node, we have similar base cases. Namely, if the linked list is empty, we return true. Or if the tree is empty, we return false.
If the values of the current linked list node and tree node are equal, then we recursively check if the rest of the linked list exists in the left subtree or right subtree.
If the values are not equal, the linked list does not exist starting from that tree node.
So, by recursively stepping through the tree and stepping through the linked list at the same time, we can efficiently determine if the linked list exists in the binary tree.

Code Implementation

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def is_sub_path(linked_list_head, root_node):
    if not linked_list_head:
        return True
    
    if not root_node:
        return False

    # Check if the linked list exists starting from each node.
    def check_sub_path_from_node(tree_node, list_node):
        if not list_node:
            return True

        if not tree_node:
            return False

        # If the values match, recursively check the subtrees.
        if tree_node.value == list_node.value:

            return check_sub_path_from_node(tree_node.left, list_node.next) or \
                   check_sub_path_from_node(tree_node.right, list_node.next)
        else:
            return False

    # Main part, finds a node that matches linked list head.
    def find_list_head_in_tree(tree_node, list_head):
        if not tree_node:
            return False

        # Check if the current node matches the list head or continue searching.
        if tree_node.value == list_head.value:

            if check_sub_path_from_node(tree_node, list_head):
                return True

        return find_list_head_in_tree(tree_node.left, list_head) or \
               find_list_head_in_tree(tree_node.right, list_head)

    # First, check if head exists in the tree
    return find_list_head_in_tree(root_node, linked_list_head)

Big(O) Analysis

Time Complexity

O(N * M) – Let N be the number of nodes in the binary tree and M be the number of nodes in the linked list. In the worst case, we might have to visit every node in the tree (N) and at each node, we potentially traverse the entire linked list (M) to check for a match starting from that node. Therefore, the overall time complexity would be O(N * M), reflecting the nested nature of searching for a potential match within the tree and then verifying if the linked list exists starting at that matching node. The worst-case time complexity occurs when the binary tree has many nodes with the same value as the head of the linked list, forcing the algorithm to explore numerous potential matches.

Space Complexity

O(H) – The primary driver of space complexity is the recursion stack due to the recursive calls in the `isSubPath` and the helper method used to check if the linked list exists starting from a tree node. In the worst-case scenario, the recursion depth is proportional to the height (H) of the binary tree, as the algorithm explores each branch. Therefore, the auxiliary space used by the call stack is O(H), where H is the height of the binary tree. In a skewed tree, H can be equal to N (number of nodes in the tree), making the worst-case space complexity O(N).

Edge Cases

Case	How to Handle
Empty linked list	Return true immediately as an empty list is considered a subtree of any binary tree.
Empty binary tree	Return false immediately if the binary tree is empty because a linked list cannot be a subtree of an empty tree.
Linked list longer than any path in the binary tree	The algorithm will eventually reach a leaf node and return false if the linked list isn't found.
Linked list and binary tree both have a single node	Check if the values of the single nodes are equal and return true if they are; otherwise, return false.
Binary tree with skewed distribution (e.g., all nodes on one side)	The algorithm will traverse the skewed side and either find the list or exhaust the path returning false.
Multiple occurrences of the linked list sequence within the binary tree	The algorithm should return true as soon as the linked list is found once.
Large binary tree and linked list leading to potential stack overflow with recursion	Consider iterative approach with explicit stack or queue to prevent stack overflow in deep trees.
Linked list values are identical to values on a non-matching path	The solution must ensure the full linked list sequence is found, not just matching individual values on different paths.