LInked List in Binary Tree

XXX. Check if Linked List is Path in Tree

Tree

Linked List

DFS

Problem Statement:

Given a binary tree and a linked list, determine if the linked list exists somewhere in the tree as a path from parent to child.

• Path must follow parent-child connections
• Path can start from any node in the tree
• Values must match exactly in order

Implementation:

public boolean isSubPath(ListNode head, TreeNode root) {
    if (root == null) return false;
    return checkPath(root, head);               // Start search from root
}

// Try to find path starting from each tree node
private boolean checkPath(TreeNode node, ListNode head) {
    if (node == null) return false;
    if (dfs(node, head)) return true;           // Check if path starts here
    
    // If not found, check in left and right subtrees
    return checkPath(node.left, head) || checkPath(node.right, head);
}

// Check if linked list matches path starting from current node
private boolean dfs(TreeNode node, ListNode head) {
    if (head == null) return true;              // Found complete match
    if (node == null) return false;             // Reached leaf without match
    if (node.val != head.val) return false;     // Values don't match
    
    // Continue checking next nodes in both structures
    return dfs(node.left, head.next) || dfs(node.right, head.next);
}

Complexity:

Time Complexity: O(N * min(L, H)) where N is number of tree nodes, L is list length, H is tree height
Space Complexity: O(H) for recursion stack, where H is tree height

Key Points:

• **Two-Level DFS**:
  • Outer DFS traverses tree to find starting points
  • Inner DFS checks for matching path from each start
  • Path can start from any node in tree
• **Early Termination**:
  • Return true when full list is matched
  • Return false on value mismatch
  • Return false when tree ends before list
• **Path Requirements**:
  • Must follow parent-child connections
  • Values must match in sequence
  • Can use either left or right child

Example:

For list [4,2,8] and tree:

     1
   /   \
  4     4
 / \   / \
2   3 2   8
        

• Start at root = 1: No match
• Try left 4: Found matching path [4,2]
• Try right 4: Found matching path [4,2,8] ✓
• Return true