Two Sum in BST - Pair with given sum

Last Updated : 20 Jan, 2025

Given the root of binary search tree (BST) and an integer target, the task is to find if there exist a pair of elements such that their sum is equal to given target.

Example:

Input: target = 12

bst

Output: True
Explanation: In the binary tree above, there are two nodes (8 and 4) that add up to 12.

Input: target = 23

bst-3

Output: False
Explanation: In the binary tree above, there are no such two nodes exists that add up to 23.

Try it on GfG Practice
redirect icon

[Expected Approach 1] Using Hash Set - O(n) time and O(n) space

The idea is that if we know one number in the pair, say x, we only need to check if the other number, target - x, exists in the tree. As we traverse the tree, we can store the values we've encountered in a HashSet. For each node, we check if target - node's value is in the hashset. If it is, we return true. If not, we add the current node's value to the set and continue traversing.

Note: This approach works for binary trees as well.

C++ 
//Driver Code Starts
// C++ code to find a pair with given sum in a Balanced BST
// Using Hash Set
#include <iostream>
#include <unordered_set>
using namespace std;

class Node{
  public:
    int data;
    Node *left, *right;
    Node(int x){
        data = x;
        left = nullptr;
        right = nullptr;
    }
};
//Driver Code Ends


// Helper function to perform DFS and check
// for the required target.
bool dfs(Node *root, unordered_set<int> &st, int target){
  
    if (root == nullptr)
        return false;

    // Check if the complement (target - current node's value)
    // exists in the set
    if (st.find(target - root->data) != st.end())
        return true;

    // Insert the current node's value into the set
    st.insert(root->data);

    // Continue the search in the left and right subtrees
    return dfs(root->left, st, target) || dfs(root->right, st, target);
}

// Main function to check if two elements
// in the BST target to target
bool findTarget(Node *root, int target){
  
    // To store visited nodes' values
    unordered_set<int> st;

    // Start DFS from the root
    return dfs(root, st, target);
}


//Driver Code Starts
int main(){
    // Constructing the following BST:
    //         7
    //        / \
    //       3   8
    //      / \   \
    //     2   4   9

    Node *root = new Node(7);
    root->left = new Node(3);
    root->right = new Node(8);
    root->left->left = new Node(2);
    root->left->right = new Node(4);
    root->right->right = new Node(9);

    int target = 12;

    // Check if there are two elements in the BST
    // that added to "target"
    if (findTarget(root, target))
        cout << "True
";
    else
        cout << "False
";

    return 0;
}
//Driver Code Ends
Java 
//Driver Code Starts
// Java code to find a pair with given sum in a Balanced BST
// Using Hash Set
import java.util.HashSet;

class Node {
    int data;
    Node left, right;

    Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GfG {
//Driver Code Ends

  
    // Helper function to perform DFS and check
    // for the required target.
    static boolean dfs(Node root, HashSet<Integer> set, int target) {
        if (root == null)
            return false;

        // Check if the complement (target - current node's value)
        // exists in the set
        if (set.contains(target - root.data))
            return true;

        // Insert the current node's value into the set
        set.add(root.data);

        // Continue the search in the left and right subtrees
        return dfs(root.left, set, target) || dfs(root.right, set, target);
    }

    // Main function to check if two elements
    // in the BST target to target
    static boolean findTarget(Node root, int target) {
        HashSet<Integer> set = new HashSet<>();
        return dfs(root, set, target);
    }


//Driver Code Starts
    public static void main(String[] args) {
        // Constructing the following BST:
        //         7
        //        / \
        //       3   8
        //      / \   \
        //     2   4   9

        Node root = new Node(7);
        root.left = new Node(3);
        root.right = new Node(8);
        root.left.left = new Node(2);
        root.left.right = new Node(4);
        root.right.right = new Node(9);

        int target = 12;

        // Check if there are two elements in the BST
        // that added to "target"
        if (findTarget(root, target))
            System.out.println("True");
        else
            System.out.println("False");
    }
}
//Driver Code Ends
Python 
#Driver Code Starts
# Python code to find a pair with given sum in a Balanced BST
# Using Hash Set

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
#Driver Code Ends


# Helper function to perform DFS and check
# for the required target.
def dfs(root, st, target):
    if root is None:
        return False

    # Check if the complement (target - current node's value)
    # exists in the set
    if target - root.data in st:
        return True

    # Insert the current node's value into the set
    st.add(root.data)

    # Continue the search in the left and right subtrees
    return dfs(root.left, st, target) or dfs(root.right, st, target)

# Main function to check if two elements
# in the BST target to target
def findTarget(root, target):
    st = set()
    return dfs(root, st, target)


#Driver Code Starts
if __name__ == "__main__":
    # Constructing the following BST:
    #         7
    #        / \
    #       3   8
    #      / \   \
    #     2   4   9

    root = Node(7)
    root.left = Node(3)
    root.right = Node(8)
    root.left.left = Node(2)
    root.left.right = Node(4)
    root.right.right = Node(9)

    target = 12

    # Check if there are two elements in the BST
    # that added to "target"
    if findTarget(root, target):
        print("True")
    else:
        print("False")
#Driver Code Ends
C# 
//Driver Code Starts
// C# code to find a pair with given sum in a Balanced BST
// Using Hash Set
using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;

    public Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GfG {
//Driver Code Ends

  
    // Helper function to perform DFS and check
    // for the required target.
    static bool dfs(Node root, HashSet<int> set, int target) {
        if (root == null)
            return false;

        // Check if the complement (target - current node's value)
        // exists in the set
        if (set.Contains(target - root.data))
            return true;

        // Insert the current node's value into the set
        set.Add(root.data);

        // Continue the search in the left and right subtrees
        return dfs(root.left, set, target) || dfs(root.right, set, target);
    }

    // Main function to check if two elements
    // in the BST target to target
    static bool findTarget(Node root, int target) {
        HashSet<int> set = new HashSet<int>();
        return dfs(root, set, target);
    }


//Driver Code Starts
    static void Main(string[] args) {
        // Constructing the following BST:
        //         7
        //        / \
        //       3   8
        //      / \   \
        //     2   4   9

        Node root = new Node(7);
        root.left = new Node(3);
        root.right = new Node(8);
        root.left.left = new Node(2);
        root.left.right = new Node(4);
        root.right.right = new Node(9);

        int target = 12;

        // Check if there are two elements in the BST
        // that added to "target"
        if (findTarget(root, target))
            Console.WriteLine("True");
        else
            Console.WriteLine("False");
    }
}
//Driver Code Ends
JavaScript 
//Driver Code Starts
// JavaScript code to find a pair with given sum in a Balanced BST
// Using Hash Set
class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}
//Driver Code Ends


// Helper function to perform DFS and check
// for the required target.
function dfs(root, set, target) {
    if (root === null)
        return false;

    // Check if the complement (target - current node's value)
    // exists in the set
    if (set.has(target - root.data))
        return true;

    // Insert the current node's value into the set
    set.add(root.data);

    // Continue the search in the left and right subtrees
    return dfs(root.left, set, target) || dfs(root.right, set, target);
}

// Main function to check if two elements
// in the BST target to target
function findTarget(root, target) {
    const set = new Set();
    return dfs(root, set, target);
}


//Driver Code Starts
// Driver Code
// Constructing the following BST:
//         7
//        / \
//       3   8
//      / \   \
//     2   4   9
const root = new Node(7);
root.left = new Node(3);
root.right = new Node(8);
root.left.left = new Node(2);
root.left.right = new Node(4);
root.right.right = new Node(9);

const target = 12;

// Check if there are two elements in the BST
// that added to "target"
if (findTarget(root, target)) {
    console.log("True");
} else {
    console.log("False");
}
//Driver Code Ends

Output
True

[Expected Approach 2] Using Inorder Traversal and Two Pointers - O(n) time and O(n) space

The idea is to create an auxiliary array and store the Inorder traversal of BST in the array. The array will be sorted as Inorder traversal of BST always produces sorted array. Now we can apply Two pointer technique to find the pair of integers with sum equal to target.
(Refer Two sum for details).

C++ 
//Driver Code Starts
// C++ code to find a pair with given sum in a Balanced BST
// Using Inorder Traversal
#include <iostream>
#include <vector>
using namespace std;

class Node {
  public:
    int data;
    Node* left;
    Node* right;

    Node(int d) {
        data = d;
        left = nullptr;
        right = nullptr;
    }
};
//Driver Code Ends


// Function to perform Inorder traversal and store the 
// elements in a vector
void inorderTraversal(Node* root, vector<int>& inorder) {
    if (root == nullptr)
        return;

    inorderTraversal(root->left, inorder);

    // Store the current node's value
    inorder.push_back(root->data);

    inorderTraversal(root->right, inorder);
}

// Function to find if there exists a pair with a 
// given sum in the BST
bool findTarget(Node* root, int target) {
    
    // Create an auxiliary array and store Inorder traversal
    vector<int> inorder;
    inorderTraversal(root, inorder); 

    // Use two-pointer technique to find the pair with given sum
    int left = 0, right = inorder.size() - 1;

    while (left < right) {
        int currentSum = inorder[left] + inorder[right];

        // If the pair is found, return true
        if (currentSum == target) 
            return true;

        // If the current sum is less than the target, 
        // move the left pointer
        if (currentSum < target)
            left++;
      
          // If the current sum is greater than 
        // the target, move the right pointer
        else
            right--;
    }

    return false;
}


//Driver Code Starts
int main(){
    // Constructing the following BST:
    //         7
    //        / \
    //       3   8
    //      / \   \
    //     2   4   9

    Node *root = new Node(7);
    root->left = new Node(3);
    root->right = new Node(8);
    root->left->left = new Node(2);
    root->left->right = new Node(4);
    root->right->right = new Node(9);

    int target = 12;

    // Check if there are two elements in the BST
    // that added to "target"
    if (findTarget(root, target))
        cout << "True
";
    else
        cout << "False
";

    return 0;
}
//Driver Code Ends
Java 
//Driver Code Starts
// Java program to find a pair with given sum in a Balanced BST
// Using Inorder Traversal

import java.util.ArrayList;

class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class GfG {
//Driver Code Ends

    
    // Function to perform Inorder traversal and store the 
    // elements in an array
    static void inorderTraversal(Node root, ArrayList<Integer> inorder) {
        if (root == null)
            return;

        inorderTraversal(root.left, inorder);

        // Store the current node's value
        inorder.add(root.data);

        inorderTraversal(root.right, inorder);
    }

    // Function to find if there exists a pair with a 
    // given sum in the BST
    static boolean findTarget(Node root, int target) {
      
        // Create an auxiliary array and store Inorder traversal
        ArrayList<Integer> inorder = new ArrayList<>();
        inorderTraversal(root, inorder);

        // Use two-pointer technique to find the pair with given sum
        int left = 0, right = inorder.size() - 1;

        while (left < right) {
            int currentSum = inorder.get(left) + inorder.get(right);

            // If the pair is found, return true
            if (currentSum == target)
                return true;

            // If the current sum is less than the target, 
            // move the left pointer
            if (currentSum < target)
                left++;
          
            // If the current sum is greater than 
            // the target, move the right pointer
            else
                right--;
        }

        return false;
    }


//Driver Code Starts
    public static void main(String[] args) {
        // Constructing the following BST:
        //         7
        //        / \
        //       3   8
        //      / \   \
        //     2   4   9

        Node root = new Node(7);
        root.left = new Node(3);
        root.right = new Node(8);
        root.left.left = new Node(2);
        root.left.right = new Node(4);
        root.right.right = new Node(9);

        int target = 12;

        // Check if there are two elements in the BST
        // that added to "target"
        if (findTarget(root, target))
            System.out.println("True");
        else
            System.out.println("False");
    }
}
//Driver Code Ends
Python 
#Driver Code Starts
# Python program to find a pair with given sum in a Balanced BST
# Using Inorder Traversal

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
#Driver Code Ends


# Function to perform Inorder traversal and store the 
# elements in an array
def inorderTraversal(root, inorder):
    if root is None:
        return

    inorderTraversal(root.left, inorder)

    # Store the current node's value
    inorder.append(root.data)

    inorderTraversal(root.right, inorder)

# Function to find if there exists a pair with a 
# given sum in the BST
def findTarget(root, target):
    # Create an auxiliary array and store Inorder traversal
    inorder = []
    inorderTraversal(root, inorder)

    # Use two-pointer technique to find the pair with given sum
    left, right = 0, len(inorder) - 1

    while left < right:
        currentSum = inorder[left] + inorder[right]

        # If the pair is found, return true
        if currentSum == target:
            return True

        # If the current sum is less than the target, 
        # move the left pointer
        if currentSum < target:
            left += 1
          
        # If the current sum is greater than 
        # the target, move the right pointer
        else:
            right -= 1

    return False


#Driver Code Starts
if __name__ == "__main__":
    # Constructing the following BST:
    #         7
    #        / \
    #       3   8
    #      / \   \
    #     2   4   9

    root = Node(7)
    root.left = Node(3)
    root.right = Node(8)
    root.left.left = Node(2)
    root.left.right = Node(4)
    root.right.right = Node(9)

    target = 12

    # Check if there are two elements in the BST
    # that added to "target"
    if findTarget(root, target):
        print("True")
    else:
        print("False")
#Driver Code Ends
C# 
//Driver Code Starts
// C# program to find a pair with given sum in a Balanced BST
// Using Inorder Traversal

using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;

    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}

class GfG {
//Driver Code Ends


    // Function to perform Inorder traversal and store the 
    // elements in a list
    static void inorderTraversal(Node root, List<int> inorder) {
        if (root == null)
            return;

        inorderTraversal(root.left, inorder);

        // Store the current node's value
        inorder.Add(root.data);

        inorderTraversal(root.right, inorder);
    }

    // Function to find if there exists a pair with a 
    // given sum in the BST
    static bool findTarget(Node root, int target) {
      
        // Create an auxiliary list and store Inorder traversal
        List<int> inorder = new List<int>();
        inorderTraversal(root, inorder);

        // Use two-pointer technique to find the pair with given sum
        int left = 0, right = inorder.Count - 1;

        while (left < right) {
            int currentSum = inorder[left] + inorder[right];

            // If the pair is found, return true
            if (currentSum == target)
                return true;

            // If the current sum is less than the target, 
            // move the left pointer
            if (currentSum < target)
                left++;
          
            // If the current sum is greater than 
            // the target, move the right pointer
            else
                right--;
        }

        return false;
    }


//Driver Code Starts
    static void Main(string[] args) {
        // Constructing the following BST:
        //         7
        //        / \
        //       3   8
        //      / \   \
        //     2   4   9

        Node root = new Node(7);
        root.left = new Node(3);
        root.right = new Node(8);
        root.left.left = new Node(2);
        root.left.right = new Node(4);
        root.right.right = new Node(9);

        int target = 12;

        // Check if there are two elements in the BST
        // that added to "target"
        if (findTarget(root, target))
            Console.WriteLine("True");
        else
            Console.WriteLine("False");
    }
}
//Driver Code Ends
JavaScript 
//Driver Code Starts
// JavaScript program to find a pair with given sum in a Balanced BST
// Using Inorder Traversal

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
//Driver Code Ends


// Function to perform Inorder traversal and store the 
// elements in an array
function inorderTraversal(root, inorder) {
    if (root === null)
        return;

    inorderTraversal(root.left, inorder);

    // Store the current node's value
    inorder.push(root.data);

    inorderTraversal(root.right, inorder);
}

// Function to find if there exists a pair with a 
// given sum in the BST
function findTarget(root, target) {

    // Create an auxiliary array and store Inorder traversal
    let inorder = [];
    inorderTraversal(root, inorder);

    // Use two-pointer technique to find the pair with given sum
    let left = 0, right = inorder.length - 1;

    while (left < right) {
        let currentSum = inorder[left] + inorder[right];

        // If the pair is found, return true
        if (currentSum === target)
            return true;

        // If the current sum is less than the target, 
        // move the left pointer
        if (currentSum < target)
            left++;
          
        // If the current sum is greater than 
        // the target, move the right pointer
        else
            right--;
    }

    return false;
}


//Driver Code Starts
// Driver Code
// Constructing the following BST:
//         7
//        / \
//       3   8
//      / \   \
//     2   4   9
const root = new Node(7);
root.left = new Node(3);
root.right = new Node(8);
root.left.left = new Node(2);
root.left.right = new Node(4);
root.right.right = new Node(9);

const target = 12;

// Check if there are two elements in the BST
// that added to "target"
if (findTarget(root, target)) {
    console.log("True");
} else {
    console.log("False");
}
//Driver Code Ends

Output
True

    

Comment

Explore