1367. Linked List in Binary Tree

Leetcode Challenge

PROBLEM STATEMENT:

Given a binary tree root and a linked list starting from head, return True if the linked list appears as a downward path in the binary tree, or False otherwise. A downward path means the linked list nodes correspond to a path in the tree where we always move downwards from one node to its child.

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:

There is a subpath in the binary tree that corresponds to the linked list [4,2,8].

EXAMPLE 2:

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:

No valid path contains all elements of the linked list from head.

APPROACH

The challenge involves recursively checking if a path starting from any node in the binary tree matches the linked list. If at any point the node values don't match or if the tree node is null, return False. Otherwise, we continue to traverse down both the left and right subtrees to find the matching path.

STEP-BY-STEP SOLUTION:

RECURSIVE CHECK:

• Define a helper function check(ListNode head, TreeNode root) that checks whether the linked list starting from head forms a downward path in the binary tree starting from root.
• BASE CASE
• If the linked list (head) is null, it means we've successfully found a valid path, so return True.
• If the tree node (root) is null or the node values don't match, return

RECURSIVE TRAVERSAL:

• The function isSubPath(ListNode head, TreeNode root) checks whether the linked list is a subpath of the binary tree by checking the current tree root and then recursively checking the left and right subtrees.

CODE IMPLEMENTATION:

class Solution
{
// Helper function that checks if the linked list starting from 'head
// is a subpath of the binary tree starting from 'root'.

private boolean check(ListNode head, TreeNode root)
{
// If we've reached the end of the linked list, it means we've found a valid path
if(head == null)
{
return true;
}

// If the tree node is null or the values don't match, the path is not valid
if(root == null || root.val != head.val)
{
return false;
}

// Recursively check the left and right subtrees
return check(head.next, root.left) || check(head.next, root.right);

// Main function to check if the linked list is a subpath of the binary tree
public boolean isSubPath(ListNode head, TreeNode root)
{
if(root == null)
{
return false;
}
// Check the current root and recursively check the left and right subtrees

return check(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
}
}        

EXPLANATION:

1. check(ListNode head, TreeNode root) : This helper function performs the main task of checking wheter the linked list is a subpath starting from the given tree node. If the current node values match, it continues checking the left and right child nodes.

isSubPath(ListNode head, TreeNode root) : This function initiates the search by checking whether the linked list forms a subpath starting from any node in the binary tree.

🔑KEY POINTS:

1. The solution efficiently checks every possible path in the binary tree where the linked list could be a subpath.
2. The recursive structure ensures that all possible paths are considered while maintaining readability and clarity.

CONCLUSION:

This solution provides an efficient way to determine if a linked list forms a downward path in a binary tree. With a recursive approach, we can easily check all possible paths in the tree, making this an optimal solution even for larger trees.