## Google Interview Question for Software Engineer / Developers

Country: United States

Comment hidden because of low score. Click to expand.
30
of 38 vote

solution : having complexity O(n)(time)+O(height of BST)(space)
observation : if we are given a sorted array instead of a BST and the same question was asked then so solve this problem in O(n)+O(1) complexity, we keep two indexes one at start and 2nd one at end, and apply following algo.

``````if(A[1st_index] + A[2nd_index] < x)
2nd_index--;
else if (A[1st_index] + A[2nd_index] > x)
1st_index++;
else
print 1st_index,2nd_index;
do this until 2nd_index > 1st_index``````

so we apply the same concept here, because we don't have data stored in an array faction, so we need some space, now one way is tot store the data into an array and apply the same, but this require O(n) space, but if you think carefully, then we only require at max 2*height_of_BST, in first array of size height_of_BST, we store all elements which comes from

``root->left,root->left->left,.......``

and in 2nd array we store

``root,root->right,root->right->right,.......``

and we start with the last element of these two array, these array's are actually stack. now we get two element do we do the same comparison here also

``````if(first_stack_element + 2nd_stack_element < x)
check for it's left tree, and store all right going element into stack(2nd stack) and start again
example :
\
6
/
3
/ \
1  4
so we store [.......3,4] after popging 6. because now 4 is the biggest element in the tree.
actually we search for last biggest element here.
else if (first_stack_element + 2nd_stack_element > x)
Here we search for next smallest element, using our 1st stack.
example
/
2
\
6
/  \
3   7
now here we go with 3 for next comparison.and the stack contain [.....,6,3] after popping 2
else
print first_stack_element, 2nd_stack_element;
do this until first_stack_element < 2nd_stack_element``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Do we need multi threads here?
I have the same logic as you. But I think I am not able to implement with single thread. Plz write code if possible

Comment hidden because of low score. Click to expand.
0

we don't actually, we apply while loop here, and store node into stack(not just values), and in each loop we do above check, (mean updating the stacks),
I will write single threaded code of it on this thursday, as i have some quizzes in this week.

Comment hidden because of low score. Click to expand.
0

I think it is great solution~

Comment hidden because of low score. Click to expand.
0

A very good solution.

Comment hidden because of low score. Click to expand.
0

Someone please provide java code or explanation for this BST (after each iteration, with contents of S1, S2) -

``````5
3        8
2    4    6 9
2.1 3.1``````

I want to search for sum=5.2

Comment hidden because of low score. Click to expand.
1

let s1 and s2 are two stack
initially s1 contain : [3,2]
and s2 contain : [5,8,9]
we sum 2 and 9 and compare then with 5.2 and 11 is bigger then 5.2 so we look for left child of 9 which is not there, so we pop 9 from s2
now stacks contains
s1 : [3,2]
s2 : [5,8]
again 2+8 > 5.2 so we pop 8 and push 6
now stacks contain :
s1 : [3,2]
s2 : [5,6]
now again 2+6 > 5.2, we pop 6 from it
now stacks contain :
s1 : [3,2]
s2 : 
again 2+5 > 5.2 so we pop 5 from it and push [3,4] into it
now stacks are :
s1 : [3,2]
s2 : [3,4]
again 2+4 > 5.3 so we pop 4 and push 3.1 into it
now stacks contains :
s1 : [3,2];
s2 : [3,3.1]
here 2+3.1 < 5.2 so we pop 2 from s1 and push 2.1 into it
now stack contains :
s1 : [3,2.1]
s2 : [3,3.1]
now 2.1 + 3.1 = 5.2 we get our answer, we print 3.1 and 2.1, if there is a possibility of having multiple pairs, then we won't stop here we go upto the condition that element of s1 is smaller then element of s2.

Comment hidden because of low score. Click to expand.
0

Test3:

``````/----9
/----8
|    \____6
5
|    /----4
|    |    \____3.1
\____3
|    /----2.1
\____2``````

Comment hidden because of low score. Click to expand.
0

Your solution didn't seem to work when the left tree only contains one node.

e.g. create the tree with 7, 20, 2, 12, 17, 22 with target 37
s1 = 
s2 = [7,20,22]
2 + 22 < 37 so you pop 2 .. now what? it has no right subtree - you can't check the left/right elements as the condition of your loop.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I forgot one thing to write here which is that root node is included in both the stacks, as i am checking the condition which is that stack1's element should be smaller then stack2's element, so this will not create any problem, but it solve problems like yours, thanks for that,
here is the execution :
s1 = [7,2]
s2 = [7,20,22]
2+22 < 37
s1 = 
s2 = [7,20,22]
7+22 < 37
s1 = [20,12]
s2 = [7,20,22]
12+22 < 37
s1 = [20 17]
s2 = [7,20,22]
17+22 > 37
s1 = [20,17]
s2 = [7,20]
17+20 = 37;

Comment hidden because of low score. Click to expand.
9

thanks - this code seems to work then:

``````public void printTwoNodeValueEqualToX(Integer value) {
Stack<BinaryNode> leftStack = new Stack<BinaryNode>();
Stack<BinaryNode> rightStack = new Stack<BinaryNode>();
BinaryNode scan = root;
while (scan != null) {
scan = scan.left;
}
scan = root;
while (scan != null) {
scan = scan.right;
}

do {
if (leftStack.peek().item + rightStack.peek().item > value) {
BinaryNode rightElem = rightStack.pop();
if (rightElem.left != null) {
scan = rightElem.left;
while (scan != null) {
scan = scan.right;
}
}
} else if (leftStack.peek().item + rightStack.peek().item < value) {
BinaryNode leftElem = leftStack.pop();
if (leftElem.right != null) {
scan = leftElem.right;
while (scan != null) {
scan = scan.left;
}
}
} else {
System.out.println(leftStack.peek().item + ", "
+ rightStack.peek().item);
return;
}
} while (leftStack.peek().item < rightStack.peek().item);

}``````

Comment hidden because of low score. Click to expand.
0

In ur code
if(A[1st_index] + A[2nd_index] < x)
it this is true then there will be no two values with the required sum x.....then why are u subtracting 2nd_index--......

Comment hidden because of low score. Click to expand.
1
of 1 vote

FOR THE OBSERVATION PART (above):
===============================

Array example is considered to be sorted in non-increasing fashion.

"
observation : if we are given a sorted array instead of a BST and the same question was asked then so solve this problem in O(n)+O(1) complexity, we keep two indexes one at start and 2nd one at end, and apply following algo.

``````if(A[1st_index] + A[2nd_index] < x)
2nd_index--;
else if (A[1st_index] + A[2nd_index] > x)
1st_index++;
else
print 1st_index,2nd_index;
do this until 2nd_index > 1st_index``````

"

Comment hidden because of low score. Click to expand.
0

Good work with printTwoNodeValueEqualToX()

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think the code 'printTwoNodeValueEqualToX()' will fail to the following test case:
{1, 2, 2, 10}, sum = 4
I think it should not use 'while (leftStack.peek().item < rightStack.peek().item);',
because in the above example, the answer is {2, 2}, with the same value in the pair.
I think it should use 'while (leftStack.peek() != rightStack.peek());'.

BTW, the follwoing is my Java implementation together with some simple tests,
I'd appreciate any bug if you found:

``````import java.util.*;

class Node
{
public Node lChild = null;
public Node rChild = null;
public int data;
public Node(int d) {data = d;}
}

class G215
{
public static Node[] findTowNodesSumTo(Node root, int sum)
{
Node n1 = root;
Node n2 = root;
Stack<Node> stack1 = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
while ((null != n1 || !stack1.isEmpty()) && (null != n2 || !stack2.isEmpty()))
{
if (null != n1) {stack1.push(n1); n1 = n1.lChild; continue;}
if (null != n2) {stack2.push(n2); n2 = n2.rChild; continue;}
if (stack1.peek() == stack2.peek()) {return null;}
int s = stack1.peek().data + stack2.peek().data;
if (s == sum)
{
Node[] result = new Node;
result = stack1.peek();
result = stack2.peek();
return result;
}
if (s > sum)
{
n2 = stack2.pop();
n2 = n2.lChild;
}
else
{
n1 = stack1.pop();
n1 = n1.rChild;
}
}
return null;
}

public static void main(String[] args)
{
// First test case
int[] array1 = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
Node tree1 = createTree(array1);
Node[] result1 = findTowNodesSumTo(tree1, 80);
System.out.println("result1:");
if (null != result1) for (Node n : result1) {System.out.println("" + n.data);}
// Second test case
int[] array2 = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
Node tree2 = createTree(array2);
Node[] result2 = findTowNodesSumTo(tree2, 72);
System.out.println("result2:");
if (null != result2) for (Node n : result2) {System.out.println("" + n.data);}
}

public static Node createTree(int[] array)
{
return createTree(array, 0, array.length - 1);
}

private static Node createTree(int[] array, int begin, int end)
{
if (begin > end) {return null;}
if (begin == end) {return new Node(array[begin]);}
int size = end - begin + 1;
int lSize = (size - 1) / 2;
Node n = new Node(array[begin + lSize]);
n.lChild = createTree(array, begin, begin + lSize - 1);
n.rChild = createTree(array, begin + lSize + 1, end);
return n;
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Isnt it like we are comparing the inorder and reverse inorder elements? This solution is pretty good.

Comment hidden because of low score. Click to expand.
0

@Alva0930 what is the running time and space for your solution? Could you please tell us?

Comment hidden because of low score. Click to expand.
0

Are your comparison operators flipped in the original post? I get the logic, based on later comment examples. However, when I look at the original post, it seems like I want to be doing the opposite of what each 'if statement' suggests to do.

Comment hidden because of low score. Click to expand.
0

Since the above code implementing @sonesh's idea is not clear enough, I submit the following simple implementation in Java:

``````public void findNodes(Node root, int sum) {
Stack<Node> left = new Stack<Node>();
Stack<Node> right = new Stack<Node>();

Node x = root;

while (x != null) {
left.push(x);
x = x.left;
}

x = root;
while (x != null) {
right.push(x);
x = x.right;
}

while (!left.isEmpty() && !right.isEmpty()) {
Node lNode = left.peek();
Node rNode = right.peek();

int s = lNode.key + rNode.key;
if (s < sum) {
left.pop();
if (lNode.right != null) {
left.push(lNode.right);
}
} else if (s > sum) {
right.pop();
if (rNode.left != null) {
right.push(rNode.left);
}
} else {
System.out.println(lNode.key + " " + rNode.key);
break;
}
}``````

}

Comment hidden because of low score. Click to expand.
3
of 3 vote

My fifty cents (full C++ solution, O(h) space complexity, O(n log n) time complexity) :

``````#include <iostream>

using namespace std;

// We need to define the structurs for BST and stacks (using linked-list)

class BSTNode {
public:
int value;
BSTNode *left;
BSTNode *right;

BSTNode(int value, BSTNode *left=NULL, BSTNode *right=NULL) {
this->value = value;
this->left = left;
this->right = right;
}
int contains(int value, BSTNode *exclude=NULL) {
if (value < this->value)
return (this->left != NULL && this->left->contains(value, exclude));
else if (value > this->value)
return (this->right != NULL && this->right->contains(value, exclude));
else
return (this == exclude) ? 0 : 1;
}
};

class LLNode {
public:
BSTNode *tree;
LLNode *next;
LLNode(BSTNode *tree, LLNode *next) {
this->tree = tree;
this->next = next;
}
};

class Stack {
public:
Stack() {
}
~Stack() {
}
}
void push(BSTNode *tree) {
}
BSTNode *pop() {
return NULL;
return ret;
}
};

/*
We performe a depth-first search on the BST using a stack which size won't
grow over O(height of the tree).
For each node we find, we check in logarithmic time whether the complement is
in the tree (taking care of excluding this node).
*/
int findNodesWithSum(BSTNode *root, int sum) {
Stack stack;
stack.push(root);
BSTNode *curTree;
while ((curTree = stack.pop()) != NULL) {
if (root->contains(sum - curTree->value, curTree)) {
cout << curTree->value << "+" << (sum - curTree->value) << endl;
return 1;
}
if (curTree->right != NULL)
stack.push(curTree->right);
if (curTree->left != NULL)
stack.push(curTree->left);
}
return 0;
}

int main(int argc, char* argv[]) {
/*
13
5               15
3       8       14      17
*/
BSTNode *root = new BSTNode(13,
new BSTNode(5,
new BSTNode(3),
new BSTNode(8)),
new BSTNode(15,
new BSTNode(14),
new BSTNode(17))
);
findNodesWithSum(root, 9);      // 5+8
findNodesWithSum(root, 20);     // 5+15
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
struct graph
{
int value;
struct graph *left;
struct graph *right;
}*root;
struct graph *creategraph(int k)
{
struct graph *temp=malloc(sizeof(struct graph));
temp->value=k;
temp->left=NULL;
temp->right=NULL;
return temp;
}
int Search(struct graph *root,struct graph *m, int diff)
{
struct graph *r=root;
while(r!=NULL)
{
if(r->value==diff && r!=m)
{
printf("First Node :%d\n",r->value);
return 1;
}
if(r->value<diff)
r=r->right;
else
r=r->left;
}
}
void Find2NodeSumisX(struct graph *k,int sum)
{
if(k==NULL)
return;
int i=0;
i=Search(root,k,sum-k->value);
if(i==1)
{
printf("Second Node Value: %d\n Found!!",k->value);
exit(0); // if You want to print all such combination of two node which give a sum of X remove exit(0)
}
if(k->value>=sum)
Find2NodeSumisX(k->left,sum); // if sum<=root->value the both required node must be in left subtree
else
{
Find2NodeSumisX(k->left,sum);
Find2NodeSumisX(k->right,sum);
}
}
int main()
{
root=creategraph(11);
root->left=creategraph(4);
root->right=creategraph(15);
root->left->left=creategraph(3);
root->left->right=creategraph(8);
root->left->left->left=creategraph(7);
root->left->left->left->left=creategraph(1);
root->right->left=creategraph(10);
root->right->right=creategraph(16);
root->right->right->right=creategraph(14);
root->right->left->left=creategraph(5);
root->right->right->right->right=creategraph(2);
int X=31;
Find2NodeSumisX(root,X);
}``````

Comment hidden because of low score. Click to expand.
0

good but brute!!!

Comment hidden because of low score. Click to expand.
0
of 2 vote

Here is solution as per space complexity, but high time complexity. If any one get soln with less complexity will be better.

``````BOOL TwoNodeSum(NODE *Root, int x, NODE **N1, NODE **N2)
{
NODE *Mn = NULL, *Mx = NULL, *List[HIGHT], *TN = NULl, *TN2 = NULl;
int sum = 0, i = 0;

Mn = min(Root);
Mx = max(Root);

while(Mn->info < Mx->info){
sum = Mn->info + Mx->info;
if(sum == x){
*N1 = Mn;
*N2 = Mx;
return TRUE;
}else if(sum > x){//Get Predecessor of Max Node i.e. of Mx
TN = Root;
i = 0;
while(Mx->info != TN->info){
List[i++] = TN;
if(Mx->info < TN->info) TN = TN->Left;
else TN = TN->Right;
}

PN = List[--i];
if(Mx->Left != NULL){
Mx = max(Mx->Left);
}else if(PN != NULL){
if(PN->Right == Mx) Mx = PN;
else{
TN2 = List[--i];
SWAP(TN2, PN);
while(PN->Left == TN2){
TN2 = List[--i];
SWAP(TN2, PN);
}
Mx = PN;
}
}else{//Get Sucessor of Min Node i.e. of Mn
TN = Root;
i = 0;
while(Mn->info != TN->info){
List[i++] = TN;
if(Mx->info < TN->info) TN = TN->Left;
else TN = TN->Right;
}
PN = List[--i];
if(Mn->Right != NULL){
Mn = min(Mn->Right);
}else if(PN != NULL){
if(PN->Left == Mn) Mn = PN;
else{
TN2 = List[--i];
SWAP(TN2, PN);
while(PN->Right == TN2){
TN2 = List[--i];
SWAP(TN2, PN);
}
Mn = PN;
}
}
}//while
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Logic :
How do you find two values whose sum equal to X in a sorted array.
- keep one pointer at start and another at end of an array and move your pointers according as per sum.

Used same logic, however instead of array, think how to do it in BST.

``````public class BSTAndValueXTwoNode {
public int index = 0;
public void printTwoNodeValueEqualToX(Node root,int x)
{
int numberOfNodes = numberOfNodes(root);
int low = 0;
int high = numberOfNodes-1;

int lowNodeValue;
int highNodeValue;

while(low<high)
{
lowNodeValue = findValueAtIndex(root, low);
highNodeValue = findValueAtIndex(root, high);
if(lowNodeValue + highNodeValue == x)
{
System.out.println(lowNodeValue + "  " + highNodeValue);
break;
}
else if(lowNodeValue + highNodeValue < x)
{
low++;
}
else
{
high--;
}
}

}
//method to find value at particular index in BST
public int findValueAtIndex(Node root,int indexT)
{
index = 0;
return findValueForIndex(root,indexT);
}
//helper method
private int findValueForIndex(Node root,int indexT)
{
if(root == null)
return -1;

int left = findValueForIndex(root.left,indexT);
if(left != -1)
return left;

if(index == indexT)
return root.n;
else
index++;
int right = findValueForIndex(root.right, indexT);
if(right != -1)
return right;

return -1;
}
//method to find total number of nodes
public int numberOfNodes(Node root)
{
if(root == null)
return 0;

if(root.left == null && root.right == null)
return 1;

return 1 + numberOfNodes(root.left) + numberOfNodes(root.right);
}

public static void main(String[] args)
{
Node root = new Node(15);

BinarySearchTree bst = new BinarySearchTree(root);
bst.insert(7);
bst.insert(20);
bst.insert(2);
bst.insert(12);
bst.insert(17);
bst.insert(22);

BSTAndValueXTwoNode value = new BSTAndValueXTwoNode();
value.printTwoNodeValueEqualToX(root,37);

}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

/*
Complexity O(nlogn) time.
O(log n) space.
Logic --
If(root < sum)
find in tree sum - root.
if( no answer found in previous step)
repeat this algorithm for left subtree of root.
move to the right subtree of root.
if (root > sum)
move to left subtree.. since all of the values in right subtree and root are useless

*/
Code

``````void searchSum(bst *head, int sum) {
bst *cand = NULL;
cout << "\n"<<head->val << " " << cand->val;
return;
}
}
else{
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

Find the least element in BST. Let it be x. Let y = k-x. Find the element that is equal to y or less than y. Traverse in inorder manner from x and in reverse inorder manner from y till either x+y = k or x==y. Use iterative inorder traversal method.

Comment hidden because of low score. Click to expand.
0

G, great solution

Comment hidden because of low score. Click to expand.
0

And the iterative (or rather, lazy) traversal can be implemented using yield. (Generator/Coroutines, as some other answer put it).

Comment hidden because of low score. Click to expand.
0

But shouldn't we take into account every possible value of x up till k? That would shoot up the complexity.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````For all nodes N in BST where N <= x/2
Check if (x-N) exists in the tree

25
16                30
8           20              35
1     10    18    22
24

x=40
All nodes <= 20    are    1, 8, 10, 16, 18, 20
Search for these pairs    (1,39), (8,32), (10,30), (16, 24), (18, 22), (20, 20)
Valid if they exist and are distinct node
(10, 30), (16, 24), (18, 22),
(20, 20) points to the same node - hence invalid``````

Comment hidden because of low score. Click to expand.
0

the additional space is not O(height).Your solution will be work in just array

Comment hidden because of low score. Click to expand.
0
of 2 vote

//simple code for comparing using left and right stack
//which is basically in order traversing using stack,
//when you are traversing in left subtree using left stack, every
//time pops, push the right child of the current node and all the
//left child of the right child.

Stack left;
while(root!=null){//initialize
left.push(root.l);
root=root.l;}

node root=left.pop();//when comparing using left stack
if(root.right!=null){
left.push(root.r);
root=root.r}
while(root!=null){
left.push(root.l);
root=root.l;}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Test1:

``````/----9266
/----9223
/----8811
|     |           /----8731
|     |     /----8697
|     \____8276
/----7853
|     |                             /----7402
|     |                       /----7261
|     |                 /----7190
|     |                 |     \____6571
|     |           /----6232
|     |           |     \____5657
|     |     /----3826
|     |     |     \____3182
|     |     |           |     /----2776
|     |     |           |     |     \____2549
|     |     |           \____1767
|     \____1032
55``````

Test2:

``````/----7993
/----7700
|     \____7574
|           \____7524
7314
|           /----5142
|     /----4634
|     |     |                       /----4225
|     |     |                       |     \____3711
|     |     |                 /----3068
|     |     |           /----2825
|     |     |           |     \____2672
|     |     |     /----2514
|     |     |     |     \____2117
|     |     |     |           \____2009
|     |     |     |                 |     /----1608
|     |     |     |                 \____1298
|     |     \____1250
|     |           \____359
\____22``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````BOOL TwoNodeSum(NODE *Root, int x, NODE **N1, NODE **N2)
{
NODE *Mn = NULL, *Mx = NULL, *List[HIGHT], *TN = NULl, *TN2 = NULl;
int sum = 0, i = 0;

Mn = min(Root);
Mx = max(Root);

while(Mn->info < Mx->info){
sum = Mn->info + Mx->info;
if(sum == x){
*N1 = Mn;
*N2 = Mx;
return TRUE;
}else if(sum > x){//Get Predecessor of Max Node i.e. of Mx
TN = Root;
i = 0;
while(Mx->info != TN->info){
List[i++] = TN;
if(Mx->info < TN->info) TN = TN->Left;
else TN = TN->Right;
}

PN = List[--i];
if(Mx->Left != NULL){
Mx = max(Mx->Left);
}else if(PN != NULL){
if(PN->Right == Mx) Mx = PN;
else{
TN2 = List[--i];
SWAP(TN2, PN);
while(PN->Left == TN2){
TN2 = List[--i];
SWAP(TN2, PN);
}
Mx = PN;
}
}else{//Get Sucessor of Min Node i.e. of Mn
TN = Root;
i = 0;
while(Mn->info != TN->info){
List[i++] = TN;
if(Mx->info < TN->info) TN = TN->Left;
else TN = TN->Right;
}
PN = List[--i];
if(Mn->Right != NULL){
Mn = min(Mn->Right);
}else if(PN != NULL){
if(PN->Left == Mn) Mn = PN;
else{
TN2 = List[--i];
SWAP(TN2, PN);
while(PN->Right == TN2){
TN2 = List[--i];
SWAP(TN2, PN);
}
Mn = PN;
}
}
}//while
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

bool find2Node(Node* root,double targetV,Node*& n1,Node*& n2){
if(root==NULL)return false;

n1=root,n2=root;
stack<Node*> st1,st2;

bool hasFound=false;
while(true){
while(n1!=NULL){
st1.push(n1);
n1=n1->left;
}
while(n2!=NULL){
st2.push(n2);
n2=n2->right;
}
if(st1.top()==st2.top())break;
double nowV=st1.top()->v+st2.top()->v;
if(nowV<targetV){
n1=st1.top()->right;
st1.pop();
}else if(nowV>targetV){
n2=st2.top()->left;
st2.pop();
}else{hasFound=true;n1=st1.top();n2=st2.top();break;}
}
return hasFound;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <stack>
using namespace std;
struct tree_node
{
struct tree_node *left;
struct tree_node *right;
int data;
};

void find_tree_sum(struct tree_node *root, int sum, struct tree_node **first, struct tree_node **second)
{
stack<struct tree_node *> small;
stack<struct tree_node *> large;

struct tree_node *temp = root;
while (temp != NULL) {
small.push(temp);
temp = temp->left;
}

temp = root;
while (temp != NULL) {
large.push(temp);
temp = temp->right;
}

*first = *second = NULL;

while (!small.empty() && !large.empty()) {
if (small.top()->data > large.top()->data) {
return;
}
int s = small.top()->data + large.top()->data;

if (s == sum) {
*first = small.top();
*second = large.top();
return;
}
if (s > sum) {
temp = small.top();
if (temp->right != NULL) {
temp = temp->right;
while (temp != NULL) {
small.push(temp);
temp = temp->left;
}
} else {
do {
temp = small.top();
small.pop();
}while (!small.empty() && small.top()->right == temp);
}
} else {
temp = large.top();
if (temp->left != NULL) {
temp = temp->left;
while (temp != NULL) {
large.push(temp);
temp = temp->right;
}
} else {
do {
temp = small.top();
small.pop();
}while (!small.empty() && small.top()->left == temp);
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

Solution: anandtechblog.blogspot.in/2010/07/given-binary-search-tree-of-n-nodes.html

Comment hidden because of low score. Click to expand.
0

BST data not modified but BST is converted to a Doubly Linked List.

O(n) time solution with O(BST_DEPTH) space as stack is consumed.

Comment hidden because of low score. Click to expand.
0
of 0 vote

One simpler solution is follow same practice as in Array of elements, for moving to previous element, use InOrderPredcessor to find previous element.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Brillant idea of sonesh, and here is my implementation code in C++:

``````#include <iostream>
#include <stack>
#include <random>
#include <vector>

struct node
{
int data;
node *left, *right;
node( int data, node* left = nullptr, node* right = nullptr ) : data(data), left(left), right(right){}
};

typedef node* BST_Iter;

struct BST
{
private:
void delete_subtree( BST_Iter it )
{
if( it != nullptr )
{
delete_subtree(it->left);
delete_subtree(it->right);
delete it;
}
}

public:
BST_Iter root;
BST() : root(nullptr) {}
~BST(){ delete_subtree(root); }

void push( int v )
{
if( root == nullptr )
{
root = new node(v);
return;
}

BST_Iter prev_it, it = root;
while( it != nullptr )
{
prev_it = it;
if( v <= it->data ) it = it->left;
else it = it->right;
}

if( v < prev_it->data ) prev_it->left = new node(v);
else prev_it->right = new node(v);
}
};

void sum_of_two( const BST& tr, int x ) // time complexity is O(n), because each node at most is push and pop from the stack by once
{
if( tr.root == nullptr ) return;

std::stack<BST_Iter> min_stack, max_stack;
BST_Iter it = tr.root;
while( it != nullptr )
{
min_stack.push(it);
it = it->left;
}
BST_Iter jt = tr.root;
while( jt != nullptr )
{
max_stack.push(jt);
jt = jt->right;
}

it = min_stack.top(), jt = max_stack.top();
min_stack.pop(), max_stack.pop();
BST_Iter kt;
while( it != jt && it->data <= jt->data )
{
if( it->data + jt->data == x ) break;
if( it->data + jt->data < x )
{
kt = it->right;
while( kt != nullptr )
{
min_stack.push(kt);
kt = kt->left;
}
if( min_stack.empty() ) break;
it = min_stack.top();
min_stack.pop();
}
else
{
kt = jt->left;
while( kt != nullptr )
{
max_stack.push(kt);
kt = kt->right;
}
if( max_stack.empty() ) break;
jt = max_stack.top();
max_stack.pop();
}
}

if( it->data + jt->data == x )
std::cout << "Elements : " << it->data << "+" << jt->data << "=" << x << std::endl;
else
std::cout << "No Elements makes the sum : " << x << std::endl;
}

int main( int argc, char* argv[] )
{
int n = 10;
int x;
std::vector<int> vec;
vec.reserve(n);
std::default_random_engine gen;
std::uniform_int_distribution<int> dist( 0, 100 );
std::cout << "Elements : ";
for( int i = 0; i < n; ++i )
{
vec.push_back( dist(gen) );
std::cout << vec.back() << " ";
}
std::cout << std::endl;

while(true)
{
std::cout << "------------------------" << std::endl;
std::cout << "Target : ";
std::cin >> x;
std::cout << std::endl;

BST tr;
for( std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it ) tr.push(*it);
sum_of_two( tr, x );
std::cout << "------------------------" << std::endl;
}

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.*;
public class CareerCup_15320677{
public static void main(String[]args){
int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
System.out.println(findMatchingPairWithBst(arr, 3));
}
private static Pair findMatchingPairWithBst(int[] arr, int target){
if (arr == null || arr.length == 0) {
return null;
}
Node root = Node.parse(arr);
fillLeft(root, leftStack);
fillRight(root, rightStack);

Node left = nextIncreasing(leftStack);
Node right = nextDecreasing(rightStack);
while(left != right){
int sum = left.val + right.val;

if (sum < target){
left = nextIncreasing(leftStack);
} else if (sum > target){
right = nextDecreasing(rightStack);
} else {
return new Pair(left.val, right.val);
}
}
return null;
}
private static void fillLeft(Node node, Deque<Node> stack){
if (node == null) {
return;
}
while(node != null){
stack.push(node);
node = node.left;
}
}
private static void fillRight(Node node, Deque<Node> stack){
if (node == null){
return;
}
while(node != null){
stack.push(node);
node = node.right;
}
}
private static Node nextIncreasing(Deque<Node> stack){
Node next = stack.pop();
fillLeft(next.right, stack);
return next;
}
private static Node nextDecreasing(Deque<Node> stack){
Node next = stack.pop();
fillRight(next.left, stack);
return next;
}
}
class Pair{
int x, y;

Pair(int x, int y){
this.x = x;
this.y = y;
}
public String toString(){
return String.format("(%d,%d)", x, y);
}
}
class Node{
int val;
Node left;
Node right;
static Node parse(int[] arr){
return parse(arr, 0, arr.length-1);
}
static Node parse(int[] arr, int lo, int hi){
if (lo > hi) {
return null;
}

int mid = lo + (hi-lo)/2;
Node node = new Node();
node.val = arr[mid];
node.left = parse(arr, lo, mid-1);
node.right = parse(arr, mid+1, hi);
return node;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void getSum(class tree* head1, class tree* head2, int sum)
{
{
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Working python solution:

``````class Node:
def __init__(self,val):
self.l_child = None
self.r_child = None
self.val     = val

def binary_insert(root,node):
if root is None:
root = node
elif(root.val > node.val):
if(root.l_child == None):
root.l_child = node
else:
binary_insert(root.l_child,node)
else:
if(root.r_child == None):
root.r_child = node
else:
binary_insert(root.r_child,node)

r = Node(8)
binary_insert(r,Node(3))
binary_insert(r,Node(1))
binary_insert(r,Node(6))
binary_insert(r,Node(4))
binary_insert(r,Node(7))
binary_insert(r,Node(10))
binary_insert(r,Node(14))
binary_insert(r,Node(13))

arr1 = []
arr2 = []

if node is None:
return
else:
arr1.append(node)

if node is None:
return
else:
arr2.append(node)

def find_sum(r,x):
if r is None:
return

while(arr1 and arr2):
if(arr1[-1].val + arr2[-1].val > x):
if(arr2[-1].l_child is None):
arr2.pop()
else:
a=arr2.pop()
arr2.append(a.l_child)
elif(arr1[-1].val + arr2[-1].val < x):
if(arr1[-1].r_child is None):
arr1.pop()
else:
a=arr1.pop()
arr1.append(a.r_child)
else:
print("result found. {} and {} sum up to {}".format(arr1[-1].val,arr2[-1].val,x))
return [arr1[-1],arr2[-1]]
break

result = find_sum(r,11)
if result is None:
print("Search not successful")``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Same solution as most guys but Python's iterator using the yield makes it particularity simpler to write out:

``````class Node:
def __init__(self, value):
self.left_child = None
self.right_child = None
self.value = value

def insert(self, value):
if value < self.value:
if self.left_child is None:
self.left_child = Node(value)
else:
self.left_child.insert(value)
else:
if self.right_child is None:
self.right_child = Node(value)
else:
self.right_child.insert(value)

def __repr__(self):
return "<" + str(hex(id(self))) + ">(" + str(self.value) + ")"

def min_iterator(self):
if self.left_child:
for node in self.left_child.min_iterator():
yield node
yield self
if self.right_child:
for node in self.right_child.min_iterator():
yield node

def max_iterator(self):
if self.right_child:
for node in self.right_child.max_iterator():
yield node
yield self
if self.left_child:
for node in self.left_child.max_iterator():
yield node

def tree_from_list(lst):
root = Node(lst)
for item in lst[1:]:
root.insert(item)
return root

def find_pair(root, sum_value):
min_iter, max_iter = root.min_iterator(), root.max_iterator()
min_node = next(min_iter)
max_node = next(max_iter)
while True:
if min_node is max_node:
return None, None

cur_sum = min_node.value + max_node.value
if cur_sum == sum_value:
return min_node, max_node
elif cur_sum > sum_value:
max_node = next(max_iter)
elif cur_sum < sum_value:
min_node = next(min_iter)

tree = tree_from_list([60, 41, 74, 16, 53, 65, 25, 46, 55, 63, 70, 42, 62, 64])

print find_pair(tree, 41 + 74)``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here is the logic for the case where all node values are positive.
Starting from root node,
IF (x <= root node value), then required two nodes with sum of values equals to x, if exists, will definitely be in left sub-tree of root
ELSE required two nodes can be in either of left or right sub-tree, in which case, find node with value (x - root.value) in tree rooted at root.

Comment hidden because of low score. Click to expand.
0

WRONG!!

Comment hidden because of low score. Click to expand.
-1
of 3 vote

coroutines!

Comment hidden because of low score. Click to expand.
0

People who don't understand should not downvote. This is an excellent (though cryptic) answer.

Comment hidden because of low score. Click to expand.
0

Yes, and to be specific, generators. Some languages like python and C# have support for it: yield.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````struct node *temp = head;

{
{
return;
}
{
return;
}

}

{
{
return;
}
{
return SUCCESS;
}

}``````

its like doing Nested Inorder inside Inorder and searching the element sum-X. (X= every node of the element)Complexity((logn)(log(n)) without extra apace ...

Comment hidden because of low score. Click to expand.
0

Your code have many bugs. Also I think your code will loop infinitely. As both functions are calling each other.

Comment hidden because of low score. Click to expand.
0

@nitin : it is just a kind of an algo..not proper code..so all boundary value cases not handled....Please let me know if any issue with Logic of an Algo..

Comment hidden because of low score. Click to expand.
0

@ravisingh: for every node you are checking the left and right subtree to see if it is equal to sum - current_node.
I think it will fit the bill.

Comment hidden because of low score. Click to expand.
0

@raviSingh - In method Nested_find_node(), you need to add check to ensure that (temp != head).

This brute force logic is coded well by

``- annn on February 18, 2013``

Comment hidden because of low score. Click to expand.
0

[CORRECTION]: Sorry not 'annn' but 'Shashi'. My bad.

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

but the size of you hash is O(n) while there is a space restriction O(height of the tree)

Comment hidden because of low score. Click to expand.
0

Nice logic though.

Comment hidden because of low score. Click to expand.
0

You don't need a hash, use two iterators one inorder (starts at min) and one reverse inorder (starts at max). Here is the C++ code, the operators ++ just return the successor in the given order. You can change the code to output one pair, unique pairs, all pair

``````// output unique pairs that sum to sum
void FindNodesWithSum(BinarySearchTree *tree, int sum)
{
InorderTraversal pre(tree);
OutoforderTraversal post(tree);
TreeNode *p, *q;
p=++pre;q=++post;
while(p && q &&p->Value()<=q->Value())
{
int sum0 = p->Value() + q->Value();
if (sum0>sum) {q=++post; }
else if (sum0<sum) { p=++pre; }
else
{
std::cout<<p->Value()<<","<<q->Value()<<"\n";
TreeNode *p0 = ++pre;
while (p0 && p->Value()==p0->Value())
{
p0=++pre;
}
TreeNode* q0 = ++post;
while (q0 && q->Value()==q0->Value())
{
q0=++post;
}
p=p0;
q=q0;
}
};
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.