1367.linked-list-in-binary-tree.md

1367. Linked List in Binary Tree

Test Cases

Edge / Corner Cases

• The linked list or tree is empty.
• The linked list is longer than the tree.

list: 1 -> 2 -> 3
tree: 
    1
   / \
  2   3

• The linked list is shorter than the tree.

list: 1
tree: 
    1
   / \
  2   3

• Tree is the subsequence of the linked list.

list: 5 -> 8
tree: 
    5
   / 
  2  
 / 
8

Approach

It's similar to 572. Subtree of Another Tree, but we need to check if the linked list is a "substring" of the tree, not a subtree. (All the node in linked list have to be in the tree, but not all tree nodes have to be in the linked list.)

fun isSubPath(head: ListNode?, root: TreeNode?): Boolean {
    if (root == null) return false
    
    // Search the linked list starting from the root node.
    return contains(head, root) ||
        isSubPath(head, root.left) || isSubPath(head, root.right) // Or search the linked list in the left and right subtree.
}

private fun contains(head: ListNode?, root: TreeNode?): Boolean {
    if (head == null && root == null) return true
    // Tree contains empty list or we reach the end of the list, then it's a subpath.
    if (head == null && root != null) return true
    // It means we have reached the end of the tree, but the linked list is not found.
    if (head != null && root == null) return false

    // Keep searching the linked list in the tree.
    return head.`val` == root.`val` && (contains(head.next, root.left) || contains(head.next, root.right))
}

• Time Complexity: O(N * M), where N is the number of nodes in the tree and M is the number of nodes in the linked list.
• Space Complexity: O(N + M), we have to travesal the tree O(N) and we check contain() which takes O(M) space in each tree node.

WA

head = 1 -> 8
root =
     1
    /
   6
  /
 8

fun isSubPath(head: ListNode?, root: TreeNode?): Boolean {
    if (head == null && root == null) return true
    if (head == null && root != null) return true
    if (head != null && root == null) return false

    val h = head!!
    val r = root!!
    val result1 = 
        h.`val` == r.`val` && (
        isSubPath(h.next, r.left) ||
        isSubPath(h.next, r.right))

    val result2 = 
        isSubPath(h, r.left) ||
        isSubPath(h, r.right)

    return result1 || result2
}

• result1 represents the case that the linked list starts from the current node in the tree. And keep searching if all the nodes in the linked list are in the tree. It's a continuation of the previous search.
• result2 represents the case that we search the beginning of the linked list in the left and right subtree of the current node. It's a new search, not a continuation of the previous search.

The problem here is that isSubPath() will check current root and also start a new search in the left and right subtree. But we should not start a new search in result1, it should be a continuation of the previous search. We should create a new function to handle the continuation of the previous search.

Corrected version:

fun isSubPath(head: ListNode?, root: TreeNode?): Boolean {
    if (head == null && root == null) return true
    if (head == null && root != null) return true
    if (head != null && root == null) return false

    val h = head!!
    val r = root!!
    // Check the current and continue the search from the previous search.
    val result1 = 
        h.`val` == r.`val` && (
        search(h.next, r.left) ||   // Modified
        search(h.next, r.right))    // Modified

    // Start a new search in the left and right subtree.
    val result2 = 
        isSubPath(h, r.left) ||
        isSubPath(h, r.right)
    
    return result1 || result2
}

// It's a continuation of the previous search.
private fun search(head: ListNode?, root: TreeNode?): Boolean {
    // Same as above.
    if (head == null && root == null) return true
    if (head == null && root != null) return true
    if (head != null && root == null) return false

    val h = head!!
    val r = root!!
    return h.`val` == r.`val` && (search(head.next, root.left) || search(head.next, root.right))
}