Two Sum IV - Input is a BST solution and explanation
Cisco
Google
9 more videos on this problem
Leetcode - Two Sum IV - Input is a BST (Python)Timothy H Chang · 3:19 · 5K views
Two Sum IV - Input is a BST | Leetcode 653 | Live coding sessionCoding Decoded · 8:50 · 3K views
LeetCode in Python 653. Two Sum IV - Input is a BST - Michelle小梦想家Michelle小梦想家 · 10:26 · 1K views
Two Sum IV - Input is a BST | LeetCode 653 | Coders CampCoders Camp · 6:37 · 937 views
LeetCode #653: Two Sum IV - Input is a BST C++ SolutionZakaria Ridouh · 6:58 · 899 views
653. Two Sum IV - Input is a BSTTech Adora by Nivedita · 9:24 · 839 views
Daily Leetcode #922: Oct 09, 2022 - 653. Two Sum IV - Input is a BSTProgramming Live with Larry · 4:26 · 655 views
653. Two Sum IV - Input is a BST | LeetCode | JavaScript | Recursion | Daily LeetCode ChallengeLeetCodeWithMonu · 2:32 · 617 views
653. Two Sum IV - Input is a BST ||LeetCode||C++ || BSTCode with Sky · 11:34 · 596 views
Daily Leetcode #510: Aug 23, 2021 - 653. Two Sum IV - Input is a BSTProgramming Live with Larry · 7:00 · 336 views
The problem
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:
- The number of nodes in the tree is in the range
[1, 104]. -104 <= Node.val <= 104rootis guaranteed to be a valid binary search tree.-105 <= k <= 105
Approach overview
Problem Overview: Given the root of a Binary Search Tree and an integer k, determine whether two distinct nodes in the tree add up to the target value. You must check if any pair of values in the BST satisfies node1.val + node2.val = k.
Approach 1: BST and HashSet Complement Search (O(n) time, O(n) space)
This approach treats the tree similarly to the classic Two Sum problem. Traverse the tree using Depth-First Search or Breadth-First Search. While visiting each node, compute the complement k - node.val and check if it already exists in a HashSet. If it does, you found a valid pair and can return true immediately. Otherwise, insert the current value into the set and continue traversing. Hash lookups run in constant time, so every node is processed once. This approach is simple, easy to implement, and works even if the tree is not balanced.
The key insight: instead of comparing every pair of nodes, store previously seen values and perform a constant-time lookup for the complement. The BST property is not heavily used here; the algorithm works on any binary tree. Time complexity is O(n) because each node is visited once. Space complexity is O(n) due to the HashSet storing up to all node values.
Approach 2: Inorder Traversal with Two-Pointer Technique (O(n) time, O(n) space)
This approach leverages the sorted nature of a Binary Search Tree. Perform an inorder traversal to collect all node values in a sorted array. Inorder traversal of a BST naturally produces values in ascending order. Once the array is built, apply the classic two-pointer technique: place one pointer at the start and another at the end of the array. Compute the sum of the two values and compare it with k.
If the sum equals k, a valid pair exists. If the sum is smaller than k, move the left pointer forward to increase the sum. If the sum is larger, move the right pointer backward to decrease the sum. Each pointer moves at most n times, so the scan runs in linear time. The traversal plus the two-pointer scan results in O(n) time overall with O(n) extra space for the array.
This technique explicitly uses the sorted order property of the BST and mirrors the optimal strategy for the classic Two Sum problem on a sorted array. It also avoids hash lookups and can be easier to reason about when debugging.
Recommended for interviews: The HashSet approach is usually the first solution interviewers expect because it directly mirrors the classic Two Sum pattern and is quick to implement during a coding interview. The inorder + two-pointer approach demonstrates deeper understanding of the BST ordering property and shows you can transform a tree problem into an array problem. Mentioning both solutions signals strong problem-solving depth.
Approach 1: Inorder Traversal with Two-Pointer Technique
This approach leverages the properties of a Binary Search Tree (BST). By performing an inorder traversal on a BST, we can obtain a sorted list of its elements. Once we have this sorted list, the problem reduces to finding two distinct numbers in this sorted array that sum up to the given target, k. This can efficiently be solved using the two-pointer technique.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def findTarget(self, root: TreeNode, k: int) -> bool:
nums = []
self.inorder(root, nums)
l, r = 0, len(nums) - 1
while l < r:
s = nums[l] + nums[r]
if s == k:
return True
elif s < k:
l += 1
else:
r -= 1
return False
def inorder(self, node, nums):
if not node:
return
self.inorder(node.left, nums)
nums.append(node.val)
self.inorder(node.right, nums)import java.util.ArrayList;
public class Solution {
public boolean findTarget(TreeNode root, int k) {
ArrayList<Integer> nums = new ArrayList<>();
inorder(root, nums);
int left = 0, right = nums.size() - 1;
while (left < right) {
int sum = nums.get(left) + nums.get(right);
if (sum == k) {
return true;
} else if (sum < k) {
left++;
} else {
right--;
}
}
return false;
}
private void inorder(TreeNode node, ArrayList<Integer> nums) {
if (node == null) return;
inorder(node.left, nums);
nums.add(node.val);
inorder(node.right, nums);
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
}#include <vector>
#include <iostream>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void inorder(TreeNode* root, std::vector<int>& nums) {
if (!root) return;
inorder(root->left, nums);
nums.push_back(root->val);
inorder(root->right, nums);
}
bool findTarget(TreeNode* root, int k) {
std::vector<int> nums;
inorder(root, nums);
int l = 0, r = nums.size() - 1;
while (l < r) {
int sum = nums[l] + nums[r];
if (sum == k) return true;
else if (sum < k) l++;
else r--;
}
return false;
}function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
var findTarget = function(root, k) {
const nums = [];
inorder(root, nums);
let left = 0, right = nums.length - 1;
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === k) {
return true;
} else if (sum < k) {
left++;
} else {
right--;
}
}
return false;
};
function inorder(node, nums) {
if (!node) return;
inorder(node.left, nums);
nums.push(node.val);
inorder(node.right, nums);
}#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void inorder(struct TreeNode* root, int* arr, int* size) {
if (root == NULL) return;
inorder(root->left, arr, size);
arr[(*size)++] = root->val;
inorder(root->right, arr, size);
}
bool findTarget(struct TreeNode* root, int k) {
int arr[10000]; // reasonable max size
int size = 0;
inorder(root, arr, &size);
int left = 0, right = size - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == k) {
return true;
} else if (sum < k) {
left++;
} else {
right--;
}
}
return false;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public bool FindTarget(TreeNode root, int k) {
List<int> nums = new List<int>();
Inorder(root, nums);
int l = 0, r = nums.Count - 1;
while (l < r) {
int sum = nums[l] + nums[r];
if (sum == k) {
return true;
} else if (sum < k) {
l++;
} else {
r--;
}
}
return false;
}
private void Inorder(TreeNode node, List<int> nums) {
if (node == null) return;
Inorder(node.left, nums);
nums.Add(node.val);
Inorder(node.right, nums);
}
}The Python solution records values via an inorder traversal. A two-pointer search checks whether any two values sum up to the target k.
Time Complexity: O(n), considering the traversal and two-pointer logic.
Space Complexity: O(n) for storing the sorted node values.
Approach 2: BST and HashSet Complement Search
This approach utilizes a hash set to store visited node values. We traverse the BST and for each node, check if k - node.val exists in the hash set. If it does, then a pair adding to k has been found.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def findTarget(self, root: TreeNode, k: int) -> bool:
self.seen = set()
return self.find(root, k)
def find(self, node, k):
if not node:
return False
if k - node.val in self.seen:
return True
self.seen.add(node.val)
return self.find(node.left, k) or self.find(node.right, k)import java.util.HashSet;
public class Solution {
public boolean findTarget(TreeNode root, int k) {
HashSet<Integer> set = new HashSet<>();
return find(root, k, set);
}
private boolean find(TreeNode node, int k, HashSet<Integer> set) {
if (node == null) return false;
if (set.contains(k - node.val)) return true;
set.add(node.val);
return find(node.left, k, set) || find(node.right, k, set);
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
}#include <unordered_set>
#include <iostream>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool findTarget(TreeNode* root, int k) {
std::unordered_set<int> set;
return find(root, k, set);
}
bool find(TreeNode* node, int k, std::unordered_set<int>& set) {
if (!node) return false;
if (set.find(k - node->val) != set.end()) return true;
set.insert(node->val);
return find(node->left, k, set) || find(node->right, k, set);
}function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
var findTarget = function(root, k) {
const set = new Set();
return find(root, k, set);
};
function find(node, k, set) {
if (!node) return false;
if (set.has(k - node.val)) return true;
set.add(node.val);
return find(node.left, k, set) || find(node.right, k, set);
}#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
bool find(struct TreeNode* root, int k, struct HashTable* table);
struct HashTable* createTable();
void insert(int val, struct HashTable* table);
bool contains(int val, struct HashTable* table);
// Assume simple HashTable implementation
bool findTarget(struct TreeNode* root, int k) {
struct HashTable* table = createTable();
return find(root, k, table);
}
bool find(struct TreeNode* node, int k, struct HashTable* table) {
if (node == NULL) return false;
if (contains(k - node->val, table)) return true;
insert(node->val, table);
return find(node->left, k, table) || find(node->right, k, table);
}
// Mock functions for table (for brevity and focus on logic)
struct HashTable* createTable() { return NULL; } // Assume implemented
void insert(int val, struct HashTable* table) { } // Assume implemented
bool contains(int val, struct HashTable* table) { return false; } // Assume implementedusing System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public bool FindTarget(TreeNode root, int k) {
HashSet<int> set = new HashSet<int>();
return Find(root, k, set);
}
private bool Find(TreeNode node, int k, HashSet<int> set) {
if (node == null) return false;
if (set.Contains(k - node.val)) return true;
set.Add(node.val);
return Find(node.left, k, set) || Find(node.right, k, set);
}
}By storing visited values in a set, the Python solution keeps track of necessary complements, rapidly determining whether k can be formed.
Time Complexity: O(n), as each node requires inspection.
Space Complexity: O(n), given the need for the set of node values.
Approach 3: Default Approach
/**
* 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);
}/**
* 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)
}// 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
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Inorder Traversal with Two-Pointer Technique | Time Complexity: O(n), considering the traversal and two-pointer logic. |
| BST and HashSet Complement Search | Time Complexity: O(n), as each node requires inspection. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BST with HashSet Complement Search | O(n) | O(n) | Best general solution. Fast to implement during interviews and works for any binary tree. |
| Inorder Traversal + Two Pointers | O(n) | O(n) | When you want to leverage BST sorted order and apply the classic two-pointer pattern. |
Frequently asked questions
Is Two Sum IV - Input is a BST easy or hard?
LeetCode classifies this problem as Easy. The main challenge is recognizing that the classic Two Sum pattern can be applied during a tree traversal or after converting the BST to a sorted array.
How to solve Two Sum IV - Input is a BST in O(n)?
Traverse the BST using DFS or BFS and maintain a HashSet of previously seen values. For each node, compute the complement k - node.val and check if it exists in the set. If found, return true; otherwise insert the current value and continue. Every node is processed once, giving O(n) time complexity.
Two Sum IV - Input is a BST Python or Java solution?
Both Python and Java implementations usually follow the same logic: traverse the BST and use a HashSet for complement lookup. Each node checks whether k - value exists in the set before inserting its own value.
What is the best approach for Two Sum IV - Input is a BST?
The HashSet complement search approach is the most practical solution. Traverse the tree and store visited values in a HashSet while checking if k - node.val already exists. This guarantees O(n) time and O(n) space and is easy to implement during interviews.
Is Two Sum IV - Input is a BST asked at Google/Amazon/Meta?
Two Sum variations frequently appear in interviews at companies like Amazon, Google, and Meta. This specific version tests understanding of binary search trees, traversal strategies, and hash-based lookup techniques.
What data structure is used in Two Sum IV - Input is a BST?
Common solutions use a HashSet to store visited node values during traversal. Another approach converts the BST to a sorted array using inorder traversal and then applies the two-pointer technique.
What is the time complexity of Two Sum IV - Input is a BST?
Optimal solutions run in O(n) time where n is the number of nodes in the tree. Each node is visited once either during traversal with a HashSet lookup or during inorder traversal followed by a two-pointer scan.