1367. Linked List in Binary Tree

This problem asks whether a given linked list exists as a downward path within a binary tree. A downward path is a sequence of nodes where each node is a parent of the next.

Approach: Depth-First Search (DFS)

The most efficient approach uses a recursive Depth-First Search (DFS) strategy. The core idea is to check if the linked list matches a path starting from each node in the binary tree.

Algorithm:

1. Base Cases:

   • If the linked list is empty (head is null or None), we've found a match, return true.
   • If the current tree node is null or None, there's no further match possible, return false.
   • If the values of the current linked list node and tree node don't match, return false.

2. Recursive Step:

   • If the values match, recursively check if the rest of the linked list (head.next) matches a path starting from either the left child (root.left) or the right child (root.right) of the current tree node. If either recursive call returns true, it means a match was found.

3. Main Function:

   • Start by checking the entire linked list against paths beginning at the root of the binary tree.
   • If no match is found at the root, recursively call the isSubPath function on the left and right subtrees of the root. This ensures we check all possible starting points in the binary tree.

Time Complexity: O(M*N), where M is the number of nodes in the binary tree and N is the number of nodes in the linked list. In the worst case, we might traverse the entire linked list against every path in the binary tree.

Space Complexity: O(M) in the worst case, due to the recursive call stack depth, which can be proportional to the height of the binary tree.

Code Implementation (Python)

# 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:
        def dfs(head, root):
            if not head:  # Base case: Linked list is empty (match found)
                return True
            if not root or head.val != root.val:  # Base case: No match or end of tree path
                return False
            return dfs(head.next, root.left) or dfs(head.next, root.right)
 
        if not root:
            return False
        return dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)

Code Implementation (Java)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if (root == null) return false;
        return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }
 
    private boolean dfs(ListNode head, TreeNode root) {
        if (head == null) return true;
        if (root == null || head.val != root.val) return false;
        return dfs(head.next, root.left) || dfs(head.next, root.right);
    }
}

The other language implementations (C++, Go, TypeScript, Rust) follow a very similar structure, adapting the syntax and data structures for their respective languages. The core recursive DFS logic remains consistent across all implementations.