Linked List in Binary Tree Solution in Java

Explore Solutions in Other Languages

Problem Description

So, you think you can just waltz into a binary tree and find a linked list? Well, think again! The problem is to determine if a given linked list is present as a path in a binary tree. Imagine a binary tree as a family tree, and the linked list as a group of friends trying to find their way through the family reunion. They need to stick together, and they can only move downwards through the tree. If they get lost, well, good luck finding them again!

In simpler terms, you need to check if the values in the linked list appear in the binary tree in the same order, while only moving downwards. If they do, congratulations! You’ve found your friends. If not, well, they might just be at the wrong party.

Code Solution


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));
  }
}

Approach

The approach here is quite straightforward. The isSubPath method checks if the linked list exists in the binary tree. It does this by calling the helper method isContinuousSubPath, which checks if the current node in the tree matches the current node in the linked list. If they match, it continues checking the next node in the linked list against the left and right children of the current tree node. If the linked list is fully traversed, it returns true.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N * M), where N is the number of nodes in the binary tree and M is the number of nodes in the linked list.
Space Complexity	O(H), where H is the height of the binary tree due to the recursion stack.

Real-World Example

Imagine you’re at a theme park, and you have a map (the linked list) that shows you the rides (the binary tree) you want to visit. You can only go down the paths (the tree nodes) that lead to the rides in the order they appear on your map. If you can follow the map without getting lost, you’re in for a fun day! If not, well, you might end up on the Ferris wheel when you were aiming for the roller coaster.