1367. Linked List in Binary Tree LeetCode Solution

In this guide, you will get 1367. Linked List in Binary Tree LeetCode Solution with the best time and space complexity. The solution to Linked List in Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Linked List in Binary Tree solution in C++
Linked List in Binary Tree solution in Java
Linked List in Binary Tree solution in Python
Additional Resources

1367. Linked List in Binary Tree LeetCode Solution image

Problem Statement of Linked List in Binary Tree

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.

Example 1:

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:

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

Example 3:

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.

Complexity Analysis

Time Complexity: O(n \cdot \min(|\texttt{head}|, h))
Space Complexity: O(\min(|\texttt{head}|, h))

1367. Linked List in Binary Tree LeetCode Solution in C++

class Solution {
 public:
  bool isSubPath(ListNode* head, TreeNode* root) {
    if (root == nullptr)
      return false;
    return isContinuousSubPath(head, root) || isSubPath(head, root->left) ||
           isSubPath(head, root->right);
  }

 private:
  bool isContinuousSubPath(ListNode* head, TreeNode* root) {
    if (head == nullptr)
      return true;
    if (root == nullptr)
      return false;
    return head->val == root->val &&
           (isContinuousSubPath(head->next, root->left) ||
            isContinuousSubPath(head->next, root->right));
  }
};
/* code provided by PROGIEZ */

1367. Linked List in Binary Tree LeetCode Solution in Java

class Solution {
  public boolean isSubPath(ListNode head, TreeNode root) {
    if (root == null)
      return false;
    return isContinuousSubPath(head, root) || isSubPath(head, root.left) ||
        isSubPath(head, root.right);
  }

  private boolean isContinuousSubPath(ListNode head, TreeNode root) {
    if (head == null)
      return true;
    if (root == null)
      return false;
    return head.val == root.val &&
        (isContinuousSubPath(head.next, root.left) || isContinuousSubPath(head.next, root.right));
  }
}
// code provided by PROGIEZ

1367. Linked List in Binary Tree LeetCode Solution in Python

class Solution:
  def isSubPath(self, head: ListNode | None, root: TreeNode | None) -> bool:
    if not root:
      return False
    return (self._isContinuousSubPath(head, root) or
            self.isSubPath(head, root.left) or
            self.isSubPath(head, root.right))

  def _isContinuousSubPath(
      self,
      head: ListNode | None,
      root: TreeNode | None,
  ) -> bool:
    if not head:
      return True
    if not root:
      return False
    return (head.val == root.val and
            (self._isContinuousSubPath(head.next, root.left) or
             self._isContinuousSubPath(head.next, root.right)))
 # code by PROGIEZ