Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Build confidence with an intuition-first walkthrough focused on hash map fundamentals.
Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.
Example 1:
Input: root = [5,3,6,2,4,null,7], k = 9 Output: true
Example 2:
Input: root = [5,3,6,2,4,null,7], k = 28 Output: false
Constraints:
[1, 104].-104 <= Node.val <= 104root is guaranteed to be a valid binary search tree.-105 <= k <= 105Problem summary: Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Two Pointers · Tree
[5,3,6,2,4,null,7] 9
[5,3,6,2,4,null,7] 28
two-sum)two-sum-ii-input-array-is-sorted)two-sum-iii-data-structure-design)two-sum-bsts)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #653: Two Sum IV - Input is a BST
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private Set<Integer> vis = new HashSet<>();
private int k;
public boolean findTarget(TreeNode root, int k) {
this.k = k;
return dfs(root);
}
private boolean dfs(TreeNode root) {
if (root == null) {
return false;
}
if (vis.contains(k - root.val)) {
return true;
}
vis.add(root.val);
return dfs(root.left) || dfs(root.right);
}
}
// Accepted solution for LeetCode #653: Two Sum IV - Input is a BST
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findTarget(root *TreeNode, k int) bool {
vis := map[int]bool{}
var dfs func(*TreeNode) bool
dfs = func(root *TreeNode) bool {
if root == nil {
return false
}
if vis[k-root.Val] {
return true
}
vis[root.Val] = true
return dfs(root.Left) || dfs(root.Right)
}
return dfs(root)
}
# Accepted solution for LeetCode #653: Two Sum IV - Input is a BST
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
def dfs(root):
if root is None:
return False
if k - root.val in vis:
return True
vis.add(root.val)
return dfs(root.left) or dfs(root.right)
vis = set()
return dfs(root)
// Accepted solution for LeetCode #653: Two Sum IV - Input is a BST
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::collections::{HashSet, VecDeque};
use std::rc::Rc;
impl Solution {
pub fn find_target(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> bool {
let mut set = HashSet::new();
let mut q = VecDeque::new();
q.push_back(root);
while let Some(node) = q.pop_front() {
if let Some(node) = node {
let mut node = node.as_ref().borrow_mut();
if set.contains(&node.val) {
return true;
}
set.insert(k - node.val);
q.push_back(node.left.take());
q.push_back(node.right.take());
}
}
false
}
}
// Accepted solution for LeetCode #653: Two Sum IV - Input is a BST
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function findTarget(root: TreeNode | null, k: number): boolean {
const dfs = (root: TreeNode | null) => {
if (!root) {
return false;
}
if (vis.has(k - root.val)) {
return true;
}
vis.add(root.val);
return dfs(root.left) || dfs(root.right);
};
const vis = new Set<number>();
return dfs(root);
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair of elements. The outer loop picks one element, the inner loop scans the rest. For n elements that is n × (n−1)/2 comparisons = O(n²). No extra memory — just two loop variables.
Each pointer traverses the array at most once. With two pointers moving inward (or both moving right), the total number of steps is bounded by n. Each comparison is O(1), giving O(n) overall. No auxiliary data structures are needed — just two index variables.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.