1367. Linked List in Binary Tree


Problem Description

The LeetCode problem presents a scenario where we have two data structures: a binary tree and a linked list. We are asked to determine if the linked list is represented by any downward path in the binary tree. A downward path in the binary tree is defined as a path that starts at any node and extends to subsequent child nodes, going downwards. The path does not need to start at the root of the binary tree. The problem requires us to create a function returning a boolean value: True if the linked list can be found as a downward path in the binary tree, and False if it cannot.

Intuition

To solve this problem, we need to traverse the binary tree and simultaneously compare the values with the nodes in the linked list. As the linked list must be followed in order, we cannot skip nodes in the linked list or in the binary tree's path. The nature of tree traversal and the need to compare it with the linked list suggest a depth-first search (DFS) approach, which allows us to explore a complete path from a node downward before moving to a sibling node.

Here's the intuition behind the solution step by step:

  1. At each node in the binary tree, we initiate a DFS to check if starting from this node, we can find a path matching the linked list.
  2. In the DFS, we compare nodes of the binary tree with the linked list in order:
    • If the current binary tree node is None, it means we've reached the bottom of a path without a mismatch; hence, if we also reached the end of the linked list (head is None), we've found a matching path.
    • If the binary tree node's value does not match the current list node's value, the current path is immediately invalid.
    • If the values match, we proceed with the next node in both the linked list and continue exploring both subtrees (left and right) of the current binary tree node.
  3. If a full linked list traversal is matched by a downward path in the binary tree (DFS returns True), we've found a corresponding path, and we return True.
  4. If not, we continue checking from the left and right children of the current binary tree node, because the path could start from either subtree.

The proposed solution is recursive in nature. It makes use of a helper function dfs to handle the downward path checking and calls dfs repeatedly for each node in the binary tree until a match is found or the entire tree is traversed without finding a corresponding path.

Learn more about Tree, Depth-First Search, Breadth-First Search, Linked List and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Solution Approach

The provided solution is a recursive algorithm that uses depth-first search (DFS) to solve the problem. Let's break down the important parts of the solution and explain the mechanics step by step:

  1. Definition of DFS Helper Function: The dfs function is a tailored depth-first search that takes two parameters—the current node of the linked list (head) and the current node of the binary tree (root). Its purpose is to check if starting from the current binary tree node, a downward path exists that corresponds to the linked list.

  2. Base Cases in DFS:

    • If the current head of the linked list is None, this means the linked list has been completely traversed, and thus, a matching path in the tree has been found. The function returns True in this case.
    • If the current root of the binary tree is None or the value of the root does not match the value of head, the path being checked does not match the linked list, and the function returns False.
  3. Recursive Step in DFS: If the current head and root values match, the algorithm proceeds by checking both the left and right children of the current binary tree node with the next node in the linked list. The dfs function is called recursively for both root.left and root.right with head.next. This recursion propagates downwards through the binary tree, building the downward path. Additionally, a logical OR is used between the recursive calls to root.left and root.right, meaning if either subtree contains a matching path, the function will return True.

  4. Primary Function Flow:

    • If the root of the binary tree is None, then there cannot be any path that matches the linked list; therefore, it returns False.
    • The primary function, isSubPath, initializes the process by calling the dfs function with the head of the linked list and root of the binary tree.
    • It also calls itself recursively for both root.left and root.right in a similar logical OR pattern. This branching out ensures that the algorithm checks all possible starting points in the binary tree for the linked list sequence.

The use of recursion for both the DFS and the overall traversal of the binary tree nodes enables the algorithm to comprehensively search for the linked list pattern within all downward paths of the tree. This approach is efficient in finding the solution, but it may not be optimal in terms of time complexity due to the multiple recursive calls and the potential for repeating work on overlapping subtrees. However, it is a clear and concise way to solve this particular problem.

Here is the critical section of the code implemented in Python, highlighting the recursive nature of the solution:

1class Solution:
2    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
3        def dfs(head, root):
4            if head is None:
5                return True
6            if root is None or root.val != head.val:
7                return False
8            return dfs(head.next, root.left) or dfs(head.next, root.right)
9
10        if root is None:
11            return False
12        return (
13            dfs(head, root)
14            or self.isSubPath(head, root.left)
15            or self.isSubPath(head, root.right)
16        )

In summary, the solution leverages recursive DFS to traverse the binary tree and matches each path with the linked list from its starting node to the end of the list to determine if a corresponding downward path exists.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Example Walkthrough

Let's illustrate the solution approach with a simple example.

Suppose we have the following binary tree:

1    1
2   / \
3  4   4
4 /     \
52       6
6       /
7      2

And the given linked list is 4 -> 2.

Now, let's walk through the solution:

Step 1: Start with the root node of the binary tree

We start with the root, which is node 1, and we compare it to the head of the linked list, which is 4. They do not match, so we proceed to check the left and right children of node 1.

Step 2: Move to the left child of the root node

The left child is node 4, which matches the head of the linked list. Now we invoke the DFS helper function to check for a downward path.

DFS Call for Node 4 (Left Child of Root)

  1. We check node 4 of the binary tree against the head of the linked list, which is also 4, and there's a match.
  2. We move to the next element in the linked list (which is 2) and to the left and right children (which are node 2 and None, respectively).
  3. Since the left child (node 2) matches the next list element, we continue the DFS call with the next element of the linked list (None, since we've reached the end) and the left child of node 2 (which is None).

At this point, the linked list has been completely matched with a downward path in the binary tree, and the DFS function returns True.

The isSubPath function would return True, signalling that the linked list 4 -> 2 is indeed a downward path in the binary tree.

If No Match Was Found

If the first DFS call did not return True, we would continue with other children of the binary tree nodes. For instance, we would also check the right child (node 4) of the root, which again matches the head of the linked list and perform DFS to explore its downward paths.

In this case, although there's another node 4, its children nodes do not continue the sequence with node 2, so the downward path that corresponds to the linked list does not exist on this side of the binary tree.

Following this approach recursively, the solution checks all potential starting nodes in the binary tree and their respective downward paths until a match is found or all possibilities are exhausted.

Solution Implementation

1class ListNode:
2    def __init__(self, value=0, next_node=None):
3        self.value = value
4        self.next_node = next_node
5
6class TreeNode:
7    def __init__(self, value=0, left=None, right=None):
8        self.value = value
9        self.left = left
10        self.right = right
11
12class Solution:
13    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
14        # Helper function to perform DFS on the binary tree
15        def dfs(linked_list_node, tree_node):
16            # If linked list is fully traversed, a subpath exists
17            if linked_list_node is None:
18                return True
19            # If tree node is None or values don't match, return False
20            if tree_node is None or tree_node.value != linked_list_node.value:
21                return False
22            # Move to next of linked list and left or right child of the tree node
23            return dfs(linked_list_node.next_node, tree_node.left) or dfs(linked_list_node.next_node, tree_node.right)
24
25        # Base case for when the binary tree is empty
26        if root is None:
27            return False
28        # Starting from this root, check for subpath or proceed to its left/right child and repeat
29        return (
30            dfs(head, root)
31            or self.isSubPath(head, root.left)
32            or self.isSubPath(head, root.right)
33        )
34
35# Note: Optional is not imported in this snippet. To use it, add: from typing import Optional
36
1// Definition for singly-linked list.
2class ListNode {
3    int val;
4    ListNode next; // Reference to the next node in the list
5
6    ListNode() {}
7
8    ListNode(int val) { this.val = val; }
9
10    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
11}
12
13// Definition for a binary tree node.
14class TreeNode {
15    int val;
16    TreeNode left; // Reference to the left child node
17    TreeNode right; // Reference to the right child node
18
19    TreeNode() {}
20
21    TreeNode(int val) { this.val = val; }
22
23    TreeNode(int val, TreeNode left, TreeNode right) {
24        this.val = val;
25        this.left = left;
26        this.right = right;
27    }
28}
29
30class Solution {
31    // Checks if there's a subpath in a binary tree that matches the values in a linked list.
32    public boolean isSubPath(ListNode head, TreeNode root) {
33        // If the binary tree is empty, there can't be a subpath.
34        if (root == null) {
35            return false;
36        }
37      
38        // Check the current path, or traverse left and right subtree to find the subpath.
39        return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
40    }
41
42    // Helper method using DFS to match the linked list with the path in the binary tree.
43    private boolean dfs(ListNode head, TreeNode root) {
44        // If we've successfully reached the end of the linked list, the subpath is found.
45        if (head == null) {
46            return true;
47        }
48      
49        // If the binary tree node is null or values do not match, this path isn't valid.
50        if (root == null || head.val != root.val) {
51            return false;
52        }
53      
54        // Continue onto the left or right subtree to find the matching subpath.
55        return dfs(head.next, root.left) || dfs(head.next, root.right);
56    }
57}
58
1/**
2 * Definition for singly-linked list.
3 */
4struct ListNode {
5    int val;
6    ListNode *next;
7    ListNode() : val(0), next(nullptr) {}
8    ListNode(int x) : val(x), next(nullptr) {}
9    ListNode(int x, ListNode *next) : val(x), next(next) {}
10};
11
12/**
13 * Definition for a binary tree node.
14 */
15struct TreeNode {
16    int val;
17    TreeNode *left;
18    TreeNode *right;
19    TreeNode() : val(0), left(nullptr), right(nullptr) {}
20    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
21    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
22};
23
24class Solution {
25public:
26    // Checks if the linked list is a subpath of the binary tree
27    bool isSubPath(ListNode* head, TreeNode* root) {
28        // If the tree node is null, the list cannot be a subpath
29        if (!root) {
30            return false;
31        }
32        // Check if the list can start from the current tree node or any subtree
33        return depthFirstSearch(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);
34    }
35
36    // Helper function to perform depth-first search starting from a tree node
37    bool depthFirstSearch(ListNode* head, TreeNode* node) {
38        // If list node is null, we've reached the end of the list successfully
39        if (!head) {
40            return true;
41        }
42        // If tree node is null or values don't match, it's not a match
43        if (!node || head->val != node->val) {
44            return false;
45        }
46        // Continue searching the rest of the list in the left and right subtrees
47        return depthFirstSearch(head->next, node->left) || depthFirstSearch(head->next, node->right);
48    }
49};
50
1// This TypeScript code defines two utility functions to determine whether
2// a linked list is a subpath of a binary tree.
3
4/**
5 * This function performs a deep-first search to check if the
6 * current linked list starting at 'head' is a subpath of the binary tree rooted at 'node'.
7 * @param {ListNode | null} head - The current node in the linked list.
8 * @param {TreeNode | null} node - The current node in the binary tree.
9 * @returns {boolean} - Returns true if the list is a subpath from the current tree node, false otherwise.
10 */
11const isSubPathFromNode = (head: ListNode | null, node: TreeNode | null): boolean => {
12    // If the linked list is exhausted, it means we've found a subpath.
13    if (head === null) { 
14        return true;
15    }
16    // If the binary tree node is null or the values do not match,
17    // the current path does not match the linked list.
18    if (node === null || head.val !== node.val) {
19        return false;
20    }
21    // Continue the search deeply in both left and right directions of the tree.
22    return isSubPathFromNode(head.next, node.left) || isSubPathFromNode(head.next, node.right);
23};
24
25/**
26 * This function checks if the linked list starting at 'head' is a subpath of the binary tree rooted at 'root'.
27 * It does so by traversing the tree nodes and, for each node, attempting to match the linked list from that starting point.
28 * @param {ListNode | null} head - The head of the linked list.
29 * @param {TreeNode | null} root - The root of the binary tree.
30 * @returns {boolean} - Returns true if the linked list is a subpath of the tree, false otherwise.
31 */
32const isSubPathOfTree = (head: ListNode | null, root: TreeNode | null): boolean => {
33    // If the root of the tree is null, the linked list cannot be a subpath.
34    if (root === null) {
35        return false;
36    }
37    // Check if the linked list is a subpath from the current root node or any of its subtrees.
38    return isSubPathFromNode(head, root) || isSubPathOfTree(head, root.left) || isSubPathOfTree(head, root.right);
39};
40
41// Note that the two methods 'isSubPathFromNode' and 'isSubPathOfTree' are to be used internally,
42// and 'isSubPathOfTree' is the entry point function equivalent to the 'isSubPath' in the original code.
43// The 'isSubPath' name was changed only because the naming convention generally favors descriptive names.
44
Not Sure What to Study? Take the 2-min Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Time and Space Complexity

The given code defines a function that checks whether a linked list is a subpath of a binary tree. The complexity is calculated based on two main operations: the dfs function that performs a deep search to compare a path in the tree with the linked list, and the recursive call isSubPath to move down the binary tree.

Time Complexity:

The time complexity of the dfs function is O(N) where N is the number of nodes in the tree. This is because, in the worst case, it might have to compare every node of the tree with the head of the linked list. Additionally, isSubPath is called for each node of the tree. Therefore, in the worst case, the time complexity becomes O(N * L) where N is the number of nodes in the binary tree and L is the length of the linked list.

Space Complexity:

The space complexity is determined by the maximum depth of the recursive call stack, which would also be proportional to the height of the tree in the worst case. Thus, the space complexity is O(H) where H is the height of the binary tree. For a skewed tree (one that resembles a linked list), the height of the tree can be N, making the space complexity O(N) in the worst case.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫