Untitled

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

public class LinkedListInBinaryTree {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if (root == null) return false;
        // Check if the path starts at this node, or continue to left and right
        return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }

    private boolean dfs(ListNode head, TreeNode node) {
        if (head == null) return true; // Reached the end of the list
        if (node == null) return false; // Tree ends before list does

        if (head.val != node.val) return false; // Values do not match

        // Continue matching the list in left or right subtree
        return dfs(head.next, node.left) || dfs(head.next, node.right);
    }

    public static void main(String[] args) {
        // Example 1
        ListNode head1 = new ListNode(4);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(8);

        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(4);
        root1.right = new TreeNode(4);
        root1.left.right = new TreeNode(2);
        root1.right.left = new TreeNode(2);
        root1.left.right.right = new TreeNode(8);

        LinkedListInBinaryTree solution = new LinkedListInBinaryTree();
        System.out.println(solution.isSubPath(head1, root1)); // Output: true

        // Example 2
        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(4);
        head2.next.next = new ListNode(2);
        head2.next.next.next = new ListNode(6);

        System.out.println(solution.isSubPath(head2, root1)); // Output: true
    }
}