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.

Flowchart Walkthrough

Let's use the algorithm flowchart to analyze LeetCode problem 1367, "Linked List in Binary Tree." Here's a detailed examination based on the provided flowchart:

Is it a graph?

  • Yes: Though the problem involves a linked list and a binary tree, they can be interpreted as graphs. The binary tree naturally forms a rooted graph structure.

Is it a tree?

  • Yes: Despite focusing on both a linked list and a binary tree, the core structure in question ā€” the binary tree ā€” is, by definition, a tree.

DFS

Given that we have identified the subject as a tree, our chart recommends using the Depth-First Search (DFS) as an appropriate algorithm strategy. In this problem, we need to determine if a sequence from the linked list appears in any path of the binary tree. DFS is suited to exploring all potential paths from any given node in the tree to look for a match that represents the sequence from the linked list.

Conclusion:

The flowchart indicates that Depth-First Search (DFS) is the correct approach for this tree-related problem, as it effectively supports a thorough examination of paths that might match the linked list sequence in various branches of the binary tree.

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.

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:

class Solution:
    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        def dfs(head, root):
            if head is None:
                return True
            if root is None or root.val != head.val:
                return False
            return dfs(head.next, root.left) or dfs(head.next, root.right)

        if root is None:
            return False
        return (
            dfs(head, root)
            or self.isSubPath(head, root.left)
            or self.isSubPath(head, root.right)
        )

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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

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

Suppose we have the following binary tree:

    1
   / \
  4   4
 /     \
2       6
       /
      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

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

In a binary min heap, the maximum element can be found in:


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More