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. Topics: Linked List, Tree, Depth-First Search, Breadth-First Search, Binary Tree. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 22 parametrized pytest cases, and a playground notebook:

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

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.

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, full suite in test_solution.py:

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.