Leetcode Daily Question 07/09/2024 - 1367. Linked List in Binary Tree

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

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

class ListNode:
  def __init__(self, val = 0, next = None):
    self.val = val
    self.next = next
    
from typing import Optional
class Solution:
  def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
    
    def dfs(node, head):
      if not head:
        return True
      if not node or node.val != head.val:
        return False
      
      return dfs(node.left, head.next) or dfs(node.right, head.next)
    
    def traversal(node):
      if node:
        return dfs(node, head) or traversal(node.left) or traversal(node.right)
    
    return traversal(root)

Explanation:

We can solve this by traversing the tree until we find a node that has the same value as the head of the linked list.

We then check if this node leads to a valid path that corresponds to the linked list. If so, then we return True.

If we traverse the entire tree without finding such a path. We return false.

We shall use two helper function to do this.

Let's define dfs for path finding.

def dfs(node, head):
  if not head:
    return True
  if not node or node.val != head.val:
    return False
  
  return dfs(node.left, head.next) or dfs(node.right, head.next)

In this function, we check if we have reached the end of the linked list. If head is None, then we have, and thus we found a match.

If we reached the end of the tree without finding a path, we return False.

We also return False if we cannot find a suitable path despite finding a potential start point.

Next, we define a second helper function to traverse the tree to find potential start point for path finding. We also initiate the path finding function here.

def traversal(node):
  if node:
    return dfs(node, head) or traversal(node.left) or traversal(node.right)
  
return traversal(root)

The time complexity is O(n) as we have to potentially traverse the entire tree to find our path.

The space complexity is O(1) as we do not need to store additional resources.

The full solution can be found near the top of the page.