Thomas Ngo

Software Engineer

3 minute read

Problem Statement

problem

Intuition

The goal is to check if a linked list is a subpath of a binary tree. A BFS approach would help us explore all possible paths starting from a match between the head of the linked list and the tree nodes. If a match is found, we traverse deeper to check if the subsequent nodes match as well.

Approach

We traverse the binary tree using a BFS (breadth-first search) approach, starting from each node in the tree that matches the value of the head of the linked list. For each matching node, we attempt to follow the path of the linked list in the tree. If we successfully match all values of the linked list in the tree, we return True. If no matching path is found, we return False.

Steps:

  1. Perform BFS from each tree node that matches the head of the linked list.
  2. At each tree node, attempt to match the next node of the linked list recursively in the left and right subtrees.
  3. If the linked list is fully matched, return True.
  4. If the traversal ends without finding a subpath, return False.

Complexity

  • Time complexity: \(O(n \times m)\) where (n) is the number of nodes in the binary tree and (m) is the length of the linked list.

  • Space complexity: The space complexity is \(O(n)\) due to the queue in BFS, where (n) is the number of nodes in the tree.

Code

# 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 bfs(self, head, root):
        queue = deque([(root, head)])
        while queue:
            node, head = queue.popleft()
            if not head: break
            if node and node.val == head.val:
                queue.append((node.left, head.next))
                queue.append((node.right, head.next))
        return head is None

    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        if not root:
            return False
        if head.val == root.val:
            if self.bfs(head, root):
                return True
        return self.isSubPath(head, root.left) or self.isSubPath(head, root.right)

Editorial

Approach 1: DFS

class Solution:
    def isSubPath(
        self, head: Optional[ListNode], root: Optional[TreeNode]
    ) -> bool:
        if root is None:
            return False
        return self._check_path(root, head)

    def _check_path(
        self, node: Optional[TreeNode], head: Optional[ListNode]
    ) -> bool:
        if node is None:
            return False
        if self._dfs(node, head):
            return True  # If a matching path is found

        # Recursively check left and right subtrees
        return self._check_path(node.left, head) or self._check_path(
            node.right, head
        )

    def _dfs(self, node: Optional[TreeNode], head: Optional[ListNode]) -> bool:
        if head is None:
            return True  # All nodes in the list matched
        if node is None:
            return False  # Reached end of tree without matching all nodes
        if node.val != head.val:
            return False  # Value mismatch
        return self._dfs(node.left, head.next) or self._dfs(
            node.right, head.next
        )
  • time: O(n * m)
  • space: O(n + m)

Approach 2: Iterative Approach

class Solution:
    def isSubPath(
        self, head: Optional[ListNode], root: Optional[TreeNode]
    ) -> bool:
        if not root:
            return False
        stack = [root]

        while stack:
            node = stack.pop()

            if self._is_match(node, head):
                return True
            # Push left and right children onto the stack
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return False

    def _is_match(
        self, node: Optional[TreeNode], lst: Optional[ListNode]
    ) -> bool:
        # Stack to keep track of (current_tree_node, current_list_node)
        stack = [(node, lst)]

        while stack:
            current_node, current_list = stack.pop()

            while current_node and current_list:
                if current_node.val != current_list.val:
                    break
                current_list = current_list.next

                # Continue to the next node in the tree, left or right
                if current_list:
                    if current_node.left:
                        stack.append((current_node.left, current_list))
                    if current_node.right:
                        stack.append((current_node.right, current_list))
                    break
            if not current_list:
                return True
        return False
  • time: O(n * m)
  • space: O(n)

You may also enjoy