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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Linked List in Binary Tree

Difficulty: Medium

Problem Description

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, a downward path means a path that starts at some node and goes downwards.

Key Insights

  • The problem requires checking if a linked list exists as a downward path in a binary tree.
  • A depth-first search (DFS) can be used to explore all paths in the binary tree.
  • We need to compare each node's value in the binary tree with the values in the linked list sequentially.
  • If any node in the binary tree matches the first node of the linked list, we can start checking the subsequent nodes from that point.

Space and Time Complexity

Time Complexity: 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. This is because we may need to check every node in the tree for every node in the linked list.

Space Complexity: O(H), where H is the height of the binary tree. This is due to the recursive call stack used in the DFS.

Solution

To solve the problem, we will implement a depth-first search (DFS) algorithm. The algorithm will traverse the binary tree and, upon encountering a node that matches the value of the linked list's head, will initiate a check to verify if the subsequent nodes in the linked list can be found in the downward path of the binary tree.

  1. Create a recursive function that checks if the current tree node matches the current linked list node.
  2. If they match, recursively check the left and right children of the current tree node for the next node in the linked list.
  3. If any of the paths match the entire linked list, return true. If the traversal completes without a match, return false.

Code Solutions

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

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

def isSubPath(head: ListNode, root: TreeNode) -> bool:
    def dfs(node, current):
        if not node:
            return False
        if not current:
            return True
        if node.val == current.val:
            # Check both children
            if dfs(node.left, current.next) or dfs(node.right, current.next):
                return True
        return False

    if not root:
        return False
    if dfs(root, head):
        return True
    return isSubPath(head, root.left) or isSubPath(head, root.right)
← Back to All Questions