Two Sum in BST Editorial

Practice Problem Link: Two Sum in BST

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given the root node of a binary search tree and a number k, find out if two nodes exist in the tree which adds up to k.

Naive Approach

The simple solution is to check each possible pair in the BST if its sum is equal to k or not. Convert the given BST into an array to check all the pairs easily.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(n)

Implementation

C++

/* This is the Node class definition

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

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
void getTraversal(Node* root, vector<int> &traversal) {
	if(root == NULL) {
		return;
	}
	getTraversal(root->left, traversal);
	traversal.push_back(root->data);
	getTraversal(root->right, traversal);
}
bool pairExists(Node* root, int k) {
	vector<int> traversal;
    getTraversal (root, traversal);
	for (int i = 0; i < traversal.size(); i++) {
		for (int j = i + 1; j < traversal.size(); j++) {
			if(traversal[i] + traversal[j] == k) {
				return true;
			}
		}
	}
	return false;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	void getTraversal(Node root, List<Integer> traversal) {
		if(root == null) {
			return;
		}
		getTraversal(root.left, traversal);
		traversal.add(root.data);
		getTraversal(root.right, traversal);
	}
	boolean pairExists(Node root, int k) {
	    List<Integer> traversal = new ArrayList<Integer>();
		getTraversal (root, traversal);
		for (int i = 0; i < traversal.size(); i++) {
			for (int j = i + 1; j < traversal.size(); j++) {
				if(traversal.get(i) + traversal.get(j) == k) {
					return true;
				}
			}
		}
		return false;
	}
}

Optimal Approach

The idea is to use a hashmap to find if the sum exists or not.

• Traverse the BST.
• Insert each value in the hashmap and also search for k - value in the hashmap.
• If k - value is found at any instance then return true otherwise return false.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

/* This is the Node class definition

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

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
bool findPair (Node* root, int k, unordered_map<int, int> &nodeData) {
	if (root == NULL) {
		return false;
	}
	if (findPair (root->left, k, nodeData)) {
		return true;
	}
	if (nodeData[k - root->data] == 1) {
		return true;
	}
	nodeData[root->data] = 1;
	if (findPair (root->right, k, nodeData)) {
		return true;
	}
	return false;
}
bool pairExists(Node* root, int k) {
    unordered_map<int, int> nodeData;
	return findPair(root, k, nodeData);
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
    boolean findPair (Node root, int k, HashMap<Integer, Integer> nodeData) {
		if (root == null) {
			return false;
		}
		if (findPair (root.left, k, nodeData)) {
			return true;
		}
		if (nodeData.get(k - root.data) != null) {
			return true;
		}
		nodeData.put(root.data, 1);
		if (findPair (root.right, k, nodeData)) {
			return true;
		}
		return false;
	}
	boolean pairExists(Node root, int k) {
	    HashMap<Integer, Integer> nodeData = new HashMap<> ();
		return findPair (root, k, nodeData);
	}
}