Marc Lester Tan

This is a fun problem as it really makes you think of how to improve your solution. There are multiple ways of solving this such as iterating through the tree and collecting all the values in a hash set. Then loop through the hash set and find if there are any entry equals to k - current element.

But the best way is to go through each node and do a binary search on the tree.

Here’s the recursive way:

import java.util.*
class Solution {
    
    val search: (Int, Int, TreeNode?) -> Boolean = { value, target, tree ->
        tailrec fun search_(node: TreeNode?): Boolean{
            if(node == null) return false
            if(node.`val` == target && node.`val` != value) return true
            
            return if(target < node.`val`) search_(node.left) else search_(node.right)
        }
        
        search_(tree)        
    }
    
    fun findTarget(root: TreeNode?, k: Int): Boolean {
        tailrec fun findTarget_(node: TreeNode?, k: Int, root: TreeNode?): Boolean{
            if(node == null) return false
            if(search(node?.`val`!!, k - node?.`val`!!, root)) return true
            return findTarget_(node.left, k, root) || findTarget_(node.right, k, root)
            
        }
        
        return findTarget_(root, k, root)
    }
}

Runtime: 224 ms, faster than 73.91% of Kotlin online submissions for Two Sum IV - Input is a BST.
Memory Usage: 38.2 MB, less than 100.00% of Kotlin online submissions for Two Sum IV - Input is a BST.

and here’s the iterative way:

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */

import java.util.*
class Solution {
    
    val search: (Int, Int, TreeNode?) -> Boolean = { value, target, tree ->
        tailrec fun search_(node: TreeNode?): Boolean{
            if(node == null) return false
            if(node.`val` == target && node.`val` != value) return true
            
            return if(target < node.`val`) search_(node.left) else search_(node.right)
        }
        
        search_(tree)        
    }
    
    fun findTarget(root: TreeNode?, k: Int): Boolean {
        if(root == null || root?.left == null && root?.right == null) return false
        
        val queue = LinkedList<TreeNode>()
        queue.offer(root)
        
        while(queue.isNotEmpty()){
            val node = queue.poll()
            if(search(node?.`val`!!, k - node?.`val`!!, root)) return true
                        
            if(node?.left != null) queue.offer(node?.left)
            if(node?.right != null) queue.offer(node?.right)
        }
        
        return false        
    }
}

Runtime: 224 ms, faster than 73.91% of Kotlin online submissions for Two Sum IV - Input is a BST.
Memory Usage: 38.5 MB, less than 100.00% of Kotlin online submissions for Two Sum IV - Input is a BST.