Two sum iv input is a bst

Hash Table Two Pointers Tree Depth-First Search Breadth-First Search Binary Search Tree Binary Tree

63.0% acceptance

Feb 20, 2026

7257

291

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to k.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashSet;
impl Solution {
  pub fn find_target(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> bool {
    let mut seen = HashSet::new();
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, k: i32, seen: &mut HashSet<i32>) -> bool {
      match node {
        None => false,
        Some(n) => {
          let b = n.borrow();
          if seen.contains(&(k - b.val)) {
            return true;
          }
          seen.insert(b.val);
          dfs(&b.left, k, seen) || dfs(&b.right, k, seen)
        }
      }
    }
    dfs(&root, k, &mut seen)
  }
}