Linked List in Binary Tree

• Define a main function isSubPath(head, root).
• If root is null, return false as no path can be formed.
• Call a helper function dfs(head, root) to check if a path matching the list starts at the current root.
• If dfs returns true, we found a match, so return true.
• Otherwise, recursively call isSubPath on the left and right children: isSubPath(head, root.left) || isSubPath(head, root.right).
• The helper function dfs(listNode, treeNode) works as follows:
• If listNode is null, return true (end of list reached).
• If treeNode is null or listNode.val != treeNode.val, return false (path broken).
• Return the result of checking the next list node against the left and right children: dfs(listNode.next, treeNode.left) || dfs(listNode.next, treeNode.right).

We define two recursive functions.

The main function, isSubPath(head, root), traverses the entire tree. Its purpose is to find a starting node in the tree that matches the head of the linked list.

• It checks three conditions:
  1. Does a path starting from the current root match the list? (This is checked by a helper function).
  2. If not, does a matching path exist in the left subtree? (Recursive call: isSubPath(head, root.left)).
  3. If not, does a matching path exist in the right subtree? (Recursive call: isSubPath(head, root.right)).
• If any of these are true, we've found a match.

The helper function, dfs(listNode, treeNode), checks if a path starting from treeNode matches the list starting from listNode.

• Base Case 1: If listNode is null, it means we've successfully matched all elements of the list. Return true.
• Base Case 2: If treeNode is null or the values don't match (treeNode.val != listNode.val), the path is broken. Return false.
• Recursive Step: If the current nodes match, we continue the search downwards. We check if the rest of the list (listNode.next) matches a path starting from either the left child (treeNode.left) or the right child (treeNode.right). Return dfs(listNode.next, treeNode.left) || dfs(listNode.next, treeNode.right).

The initial call is isSubPath(head, root).

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11/**12 * Definition for a binary tree node.13 * public class TreeNode {14 *     int val;15 *     TreeNode left;16 *     TreeNode right;17 *     TreeNode() {}18 *     TreeNode(int val) { this.val = val; }19 *     TreeNode(int val, TreeNode left, TreeNode right) {20 *         this.val = val;21 *         this.left = left;22 *         this.right = right;23 *     }24 * }25 */26class Solution {27    public boolean isSubPath(ListNode head, TreeNode root) {28        if (root == null) {29            return false;30        }31        // Check if a path starts from the current root32        if (dfs(head, root)) {33            return true;34        }35        // If not, check the left and right subtrees36        return isSubPath(head, root.left) || isSubPath(head, root.right);37    }38 39    // Helper function to check for a matching path from a given tree node40    private boolean dfs(ListNode head, TreeNode root) {41        // Base case: If we've reached the end of the list, we found a match42        if (head == null) {43            return true;44        }45        // Base case: If we've run out of tree nodes or values don't match46        if (root == null || head.val != root.val) {47            return false;48        }49        // Recursive step: Check left and right children for the next list node50        return dfs(head.next, root.left) || dfs(head.next, root.right);51    }52}