# 07.09.2024 [1367. Linked List in Binary Tree]

Is the LinkedList in the BinaryTree? #medium #linked_list #tree

07.09.2024

1367. Linked List in Binary Tree medium
blog post

youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/727

Problem TLDR

Is the LinkedList in the BinaryTree? #medium #linked_list #tree

Intuition

The problem size n is not that big, we can do a full Depth-First search and try to match Linked List at every tree node.

Approach

• the corner case is: list: [1,2], tree: [1->1->2]

Complexity

• Time complexity:
  𝑂(𝑛^2)

• Space complexity:
  𝑂(𝑛)

Code

    fun isSubPath(head: ListNode?, root: TreeNode?, start: Boolean = false): Boolean =
        head == null || head.`val` == root?.`val` && 
        (isSubPath(head.next, root.left, true) || isSubPath(head.next, root.right, true))
        || root != null && !start && (isSubPath(head, root.left) || isSubPath(head, root.right))

    pub fn is_sub_path(head: Option<Box<ListNode>>, root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        fn dfs(head: &Option<Box<ListNode>>, root: &Option<Rc<RefCell<TreeNode>>>, start: bool) -> bool {
            let Some(h) = head else { return true }; let Some(r) = root else { return false };
            let r = r.borrow();
            h.val == r.val && (dfs(&h.next, &r.left, true) || dfs(&h.next, &r.right, true))
            || !start && (dfs(head, &r.left, false) || dfs(head, &r.right, false))
        }
        dfs(&head, &root, false)
    }

    bool isSubPath(ListNode* head, TreeNode* root, bool start = 0) {
        return !head || root && root->val == head->val 
        && (isSubPath(head->next, root->left, 1) || isSubPath(head->next, root->right, 1))
        || root && !start && (isSubPath(head, root->left) || isSubPath(head, root->right));
    }