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

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.