# 1367. Linked List in Binary Tree

Given a binary tree `root` and a linked list with `head` as the first node.&#x20;

Return True if all the elements in the linked list starting from the `head` correspond to some *downward path* connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/02/12/sample_1_1720.png)

<pre><code><strong>Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
</strong><strong>Output: true
</strong><strong>Explanation: Nodes in blue form a subpath in the binary Tree.  
</strong></code></pre>

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/02/12/sample_2_1720.png)

<pre><code><strong>Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
</strong><strong>Output: true
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
</strong><strong>Output: false
</strong><strong>Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.
</strong></code></pre>

**Constraints:**

* The number of nodes in the tree will be in the range `[1, 2500]`.
* The number of nodes in the list will be in the range `[1, 100]`.
* `1 <= Node.val <= 100` for each node in the linked list and binary tree.

***My Solutions:***

```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;
        if (head.val == root.val) {
            if (search(head, root)) return true;
        }
        return isSubPath(head, root.left) || isSubPath(head, root.right);
    }
    public boolean search(ListNode list, TreeNode tree) {
        //if tree node reached to end, check list node reached to end or node
        if (tree == null) return list == null;
        // if list node reached to the end, it means every list node has been found
        if (list == null) return true;

        if (tree.val != list.val) return false;

        return search(list.next, tree.left) || search(list.next, tree.right);
    }
}
```
