653.two-sum-iv-input-is-a-bst.md

653. Two Sum IV - Input is a BST

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

Inorder + Two Pointers

private val inorder = mutableListOf<Int>()

fun findTarget(root: TreeNode?, k: Int): Boolean {
    inorder(root)
    var left = 0
    var right = inorder.size - 1
    while (left < right) {
        val sum = inorder[left] + inorder[right]
        if (sum == k) return true
        if (sum < k) left++
        else right--
    }
    return false
}

private fun inorder(root: TreeNode?) {
    if (root == null) return
    if (root.left != null) inorder(root.left)
    inorder.add(root.`val`)
    if (root.right != null) inorder(root.right)
}

• Time Complexity: O(n).
• Space Complexity: O(n) for inorder traversal.

Hash Table

private val hashSet = hashSetOf<Int>()

fun findTarget(root: TreeNode?, k: Int): Boolean {
    if (root == null) return false
    val remaining = k - root.`val`
    if (hashSet.contains(remaining)) return true
    hashSet.add(remaining)
    return findTarget(root.left, k) || findTarget(root.right, k)
}

• Time Complexity: O(n).
• Space Complexity: O(n).

Inorder Recursive Traversal

fun findTarget(root: TreeNode?, k: Int): Boolean {
    return inorder(root, k, hashSetOf<Int>())
}

private fun inorder(root: TreeNode?, k: Int, seen: HashSet<Int>): Boolean {
    if (root == null) return false
    val leftResult = if (root.left != null) inorder(root.left, k, seen) else false
    if (leftResult) return true
    val currentResult = if (seen.contains(k - root.`val`)) {
        true
    } else {
        seen.add(root.`val`)
        false
    }
    if (currentResult) return true
    val rightResult = if (root.right != null) inorder(root.right, k, seen) else false
    return leftResult || currentResult || rightResult
}