> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Linked List in Binary Tree Python Solution

> Tested Python solution for LeetCode 1367 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 1367, [Medium](/catalog/medium). Topics: [Linked List](/catalog/topics/linked-list), [Tree](/catalog/topics/tree), [Depth-First Search](/catalog/topics/depth-first-search), [Breadth-First Search](/catalog/topics/breadth-first-search), [Binary Tree](/catalog/topics/binary-tree). [View on LeetCode](https://leetcode.com/problems/linked-list-in-binary-tree/description/).

Generate this problem as a practice environment: tested reference solution, 22 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1367   # by problem number
lcpy gen -s linked_list_in_binary_tree   # by problem name
```

## Problem

Given a binary tree root and a linked list with head as the first node. 

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.

### Examples

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

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

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

```
Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
```

```
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]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.
```

### 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.

**Follow up:** What if you cannot modify the input lists, i.e. reversing them is not allowed?

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/linked_list_in_binary_tree/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/linked_list_in_binary_tree/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from leetcode_py import ListNode, TreeNode


class Solution:
    # Time: O(n * m) worst case (n tree nodes, m list length)
    # Space: O(h) recursion depth
    def is_sub_path(self, head: ListNode[int] | None, root: TreeNode[int] | None) -> bool:
        if root is None:
            return False

        def match(node: TreeNode[int] | None, cur: ListNode[int] | None) -> bool:
            if cur is None:
                return True
            if node is None or node.val != cur.val:
                return False
            return match(node.left, cur.next) or match(node.right, cur.next)

        def dfs(node: TreeNode[int] | None) -> bool:
            if node is None:
                return False
            return match(node, head) or dfs(node.left) or dfs(node.right)

        return dfs(root)
```

## Complexity

| Time | Space |
| - | - |
| O(n \* m) worst case (n tree nodes, m list length) | O(h) recursion depth |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.