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

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.

Similar Problems

Subtree of Another Tree Problem

Solution

Method 1 - Brute Force DFS

To solve this problem using Depth-First Search (DFS), we’ll follow these steps:

  1. Traverse the Tree:
    • We’ll start by traversing the binary tree from every node to find a node that matches the head of the linked list.
  2. Match Path:
    • Once we find a potential starting node in the tree that matches the head of the linked list, we use DFS to check if this node and its descendants match the linked list.
  3. Recursive Checking:
    • We’ll recursively check the left and right children of the current tree node to see if they continue to match the subsequent nodes in the linked list.
    • If at any point the values of the linked list node and the tree node do not match, or if we reach the end of the tree path with remaining nodes in the linked list, we backtrack and try another path.

Video Explanation\

Here is the video epxlanation:

Code

Java
class Solution {

	public boolean isSubPath(ListNode head, TreeNode root) {
		//  checking for root here, 
		// as isSubPath is traversed for both left and right
		// can result in NPE otherwise
		if (root == null) {
			return false;
		}
		// Path can start from root => dfs
		// Otherwise it can exist in left or right side
		return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
	}

	private boolean dfs(ListNode head, TreeNode root) {
		if (head == null) {
			return true; // Reached end of linked list, so it matches.
		}

		if (root == null) {
			return false; // Reached the end of a path in the tree with list nodes remaining.
		}
		
		return head.val == root.val && (dfs(head.next, root.left) || dfs(head.next, root.right));
	}
}
Python
class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        if not root:
            return (
                False  # Avoid NullPointerException by checking if root is null.
            )

        # Path can start from root => dfs
        # Otherwise it can exist in left or right subtree
        return (
            self.dfs(head, root)
            or self.isSubPath(head, root.left)
            or self.isSubPath(head, root.right)
        )

    def dfs(self, head: ListNode, root: TreeNode) -> bool:
        if not head:
            return True  # Reached end of linked list, so it matches.

        if not root:
            return False  # Reached the end of a path in the tree with list nodes remaining.

        return head.val == root.val and (
            self.dfs(head.next, root.left) or self.dfs(head.next, root.right)
        )

Complexity

  • Time: O(n * min(m, h)) where n is tree size, m is list size and h is the height of the tree.
  • Space: O(h) assuming recursion stack

%%

Method 2 - Use KMP

Find the Index of the First Occurrence in a String

%%