Code Implementation

# 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:
        if not root:
            return False
        def dfs(tree, list_head):
            if not list_head:
                return True
            if not tree:
                return False
            if tree.val != list_head.val:
                return False
            return dfs(tree.left, list_head.next) or dfs(tree.right, list_head.next)
        
        return (dfs(root, head) or 
                self.isSubPath(head, root.left) or 
                self.isSubPath(head, root.right))
      

// Definition for singly-linked list.
// struct ListNode {
//     int val;
//     ListNode *next;
//     ListNode() : val(0), next(nullptr) {}
//     ListNode(int x) : val(x), next(nullptr) {}
//     ListNode(int x, ListNode *next) : val(x), next(next) {}
// };
// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// };
class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        if (!root) return false;
        return dfs(root, head) || isSubPath(head, root->left) || isSubPath(head, root->right);
    }
    bool dfs(TreeNode* node, ListNode* head) {
        if (!head) return true;
        if (!node) return false;
        if (node->val != head->val) return false;
        return dfs(node->left, head->next) || dfs(node->right, head->next);
    }
};
      

// 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(root, head) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }
    private boolean dfs(TreeNode node, ListNode head) {
        if (head == null) return true;
        if (node == null) return false;
        if (node.val != head.val) return false;
        return dfs(node.left, head.next) || dfs(node.right, head.next);
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {ListNode} head
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSubPath = function(head, root) {
    if (!root) return false;
    function dfs(node, listNode) {
        if (!listNode) return true;
        if (!node) return false;
        if (node.val !== listNode.val) return false;
        return dfs(node.left, listNode.next) || dfs(node.right, listNode.next);
    }
    return dfs(root, head) || isSubPath(head, root.left) || isSubPath(head, root.right);
};
      

Problem Description

You are given the head of a singly linked list head and the root node of a binary tree root. Your task is to determine whether there exists a downward path in the binary tree (starting from any node and moving only to its children) such that the sequence of values along this path is the same as the sequence of values in the linked list.

• The path must move from parent to child (either left or right) at each step.
• The path can start from any node in the binary tree, not necessarily the root.
• Each node in the binary tree can only be used once per path.
• You must not reuse elements from the linked list or the binary tree for the same path.
• Return true if such a path exists, false otherwise.

Thought Process

At first glance, the problem seems to require checking every possible path in the binary tree and comparing it to the linked list. The straightforward way is to try to match the linked list starting from every node in the tree. For each tree node, we attempt to "walk" down the tree and the list at the same time, matching their values. If at any point the values do not match, or the tree path ends before the list, that path fails.

However, this brute-force approach can be inefficient if the tree and list are large. We may end up repeating the same checks multiple times. To optimize, we can use recursion to check for matches and terminate early as soon as a mismatch is found. Since the binary tree can branch in two directions, we need to check both left and right children at each step.

The key insight is that for each node in the tree, we need to check two things:

• Does a path starting at this node match the linked list?
• If not, recursively check the left and right subtrees.

Solution Approach

The solution uses a recursive, depth-first search (DFS) strategy to compare the linked list with every possible downward path in the binary tree. Here's how it works:

1. Define a helper function: Create a function (let's call it dfs) that takes a tree node and a list node as arguments. This function checks if the path starting from the current tree node matches the remaining linked list.
2. Base cases:
   • If the list node is null, it means we've matched the entire list, so return true.
   • If the tree node is null but the list isn't finished, return false.
   • If the values at the current tree node and list node do not match, return false.
3. Recursive step:
   • Recursively check both the left and right children of the current tree node, moving to the next node in the linked list.
   • If either returns true, the path is found.
4. Try every starting point:
   • For every node in the binary tree, call the dfs function with the head of the linked list. If a match isn't found, recursively check the left and right subtrees with the original head of the list.
5. Return the result: If any path matches, return true; otherwise, return false.

This approach ensures we efficiently check every possible starting point and path in the binary tree without unnecessary recomputation.

Example Walkthrough

Let's walk through a concrete example:

Suppose the linked list is 1 -> 4 -> 2, and the binary tree is:

        1
       / \
      4   4
     /   /
    2   2
   /   /
  1   6
  

1. Start at the root node (value 1). The first value matches the head of the list.
2. Move to the left child (value 4). This matches the second node of the list.
3. Move to the left child again (value 2). This matches the third node of the list.
4. The next node in the list is null, so we have matched the entire list. Return true.

The function would return true because a downward path matching the linked list exists in the tree.

Time and Space Complexity

Brute-force approach:

• For every node in the tree (N nodes), check every possible path of length up to the length of the linked list (L nodes).
• Time complexity: O(N * L) in the worst case.
• Space complexity: O(L) for the recursion stack (in the worst case, the path matches the entire linked list).

• Still O(N * L) in the worst case, since we may need to check the linked list at every node in the tree.
• Space complexity: O(L) for the recursion stack during a path match, plus O(H) for the tree recursion, where H is the height of the tree.
• No additional data structures are used, so space usage is efficient.

Summary

In summary, the "Linked List in Binary Tree" problem is solved by recursively checking every possible downward path in the binary tree to see if it matches the given linked list. The approach is elegant because it combines a depth-first search with careful handling of base cases, allowing for early termination and efficient traversal. By leveraging recursion, we ensure that all possible starting points are considered, and the solution remains concise and clear.