We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Linked List in Binary Tree

Number: 1484

Difficulty: Medium

Paid? No

Companies: Meta, Bloomberg, Google, SoundHound

Problem Description

Given the head of a singly linked list and the root of a binary tree, determine if there exists a downward path in the tree (starting from any node and moving only to left or right children) that contains the nodes of the linked list in order.

Key Insights

  • Use a DFS approach to traverse the binary tree starting at every node.
  • For each tree node, initiate a matching process that compares the tree values with the linked list values.
  • If the current tree node matches the current linked list node, recursively check if either the left or right child can match the next linked list node.
  • The problem is similar to a “pattern matching” scenario where the pattern is the linked list and the text is the tree's downward path.

Space and Time Complexity

Time Complexity: O(N * L) where N is the number of nodes in the tree and L is the length of the linked list.
Space Complexity: O(H + L) where H is the height of the tree (recursion stack for tree traversal) and L is the maximum recursion depth for linked list matching.

Solution

We perform a DFS traversal on the binary tree. At each node, we check if we can start a matching process with the head of the linked list. The matching function uses recursion to verify if the current tree node matches the current linked list node and then continues to check if either subtree (left or right) can follow the next linked list node. If a complete match is found (i.e. the linked list becomes null), the function returns true, indicating that a downward path exists in the tree that matches the linked list.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        # Helper function that checks if starting at tree node `node`
        # we can match the entire linked list starting from `head`
        def dfs_match(node, list_node):
            # If linked list is exhausted, we have a match.
            if not list_node:
                return True
            # If tree node is null, no match possible.
            if not node:
                return False
            # If current values match, explore both left and right subtrees for the next list node.
            if node.val == list_node.val:
                return dfs_match(node.left, list_node.next) or dfs_match(node.right, list_node.next)
            return False

        # DFS along the binary tree to try matching from every node.
        def dfs_tree(node):
            if not node:
                return False
            # Start a match from current node, or keep looking in the left/right subtree.
            return dfs_match(node, head) or dfs_tree(node.left) or dfs_tree(node.right)
        
        return dfs_tree(root)
← Back to All Questions