Google Interview Question for Software Engineer / Developers


Country: United States




Comment hidden because of low score. Click to expand.
29
of 37 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

- sonesh January 26, 2013 | Flag Reply
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

- Vincent January 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- sonesh January 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it is great solution~

- will January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

A very good solution.

- yingsun1228 January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Biru January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 votes

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 : [5]
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.

- sonesh January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Test3:

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

- Anonymous January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 = [2]
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.

- Anonymous January 28, 2013 | Flag
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 = [7]
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;

- sonesh January 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
7
of 7 votes

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) {
			leftStack.add(scan);
			scan = scan.left;
		}
		scan = root;
		while (scan != null) {
			rightStack.add(scan);
			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) {
						rightStack.add(scan);
						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) {
						leftStack.add(scan);
						scan = scan.left;
					}
				}
			} else {
				System.out.println(leftStack.peek().item + ", "
						+ rightStack.peek().item);
				return;
			}
		} while (leftStack.peek().item < rightStack.peek().item);

		System.out.println("not found");
	}

- Anonymous January 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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--......

- Anonymous February 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

To readers,

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

"

- ogle February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good work with printTwoNodeValueEqualToX()

- shruthimr February 26, 2013 | Flag
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[2];
    result[0] = stack1.peek();
    result[1] = 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;
 }
}

- Alva0930 March 01, 2013 | Flag
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.

- anirudh6kb June 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous September 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Jonathan March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
			}
		}

}

- thaghost October 07, 2014 | Flag
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:
    LLNode *head;
    Stack() {
        this->head = NULL;
    }
    ~Stack() {
        LLNode *oldHead;
        while (this->head != NULL) {
            oldHead = this->head;
            this->head = oldHead->next;
            delete oldHead;
        }
    }
    void push(BSTNode *tree) {
        this->head = new LLNode(tree, this->head);
    }
    BSTNode *pop() {
        LLNode *oldHead = this->head;
        if (oldHead == NULL)
            return NULL;
        BSTNode *ret = oldHead->tree;
        this->head = oldHead->next;
        delete oldHead;
        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, 10);     // Not found
    findNodesWithSum(root, 9);      // 5+8
    findNodesWithSum(root, 13);     // Not found
    findNodesWithSum(root, 20);     // 5+15
    return 0;
}

- Thomas February 01, 2014 | Flag Reply
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);
}

- Shashi January 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good but brute!!!

- bhushan.vibhuti January 26, 2013 | Flag
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
}

- SRB January 26, 2013 | Flag Reply
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);
		
		
	}

- Gopal January 26, 2013 | Flag Reply
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;
    bst *treeHead=head;
    while (head) {
        if (head->val < sum) {
            cand = search(treeHead, sum - head->val);
            if (cand && cand!=head) {
                cout << "\n"<<head->val << " " << cand->val;
                return;
            }
        }
        if (head->val > sum)
            head = head->l;
        else{
            searchSum(head->l,sum);
            head = head->r;
        }
    }
}

- isandesh7 January 26, 2013 | Flag Reply
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.

- Ashish Anand January 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

G, great solution

- Vincent January 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous January 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Abhirup.Dutta1989 January 28, 2013 | Flag
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

- sme January 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- will January 28, 2013 | Flag
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;}

- zyfo2 January 28, 2013 | Flag Reply
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

- Anonymous January 28, 2013 | Flag Reply
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
}

- SRB January 30, 2013 | Flag Reply
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;
}

- Anonymous February 17, 2013 | Flag Reply
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);
			}
		}
	}
}

- annn February 18, 2013 | Flag Reply
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

- A February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- A February 22, 2013 | Flag
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.

- BVMR August 02, 2013 | Flag Reply
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;
}

- weijjcg August 18, 2013 | Flag Reply
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);
                Deque<Node> leftStack = new LinkedList<Node>();
                Deque<Node> rightStack = new LinkedList<Node>();
                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;
        }
}

- madno April 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void getSum(class tree* head1, class tree* head2, int sum)
{
    if(head1 && head2)
    {
        getSum(head1->left, head2->right, sum);
        if(head1->data + head2->data == sum)
            cout<<"   Sum = "<<head1->data<<" + "<<head2->data<<endl;
        getSum(head1->right, head2->left, sum);
    }
}

- skum July 25, 2015 | Flag Reply
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 = []

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

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

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

    add_to_arr1(r.l_child)
    add_to_arr2(r)
    
    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")

- bluepulse5577 September 18, 2015 | Flag Reply
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[0])
    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)

- ramibotros August 09, 2016 | Flag Reply
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.

- kuldeep January 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

WRONG!!

- X February 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

coroutines!

- Guest uninvited January 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous January 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous January 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

struct node *temp = head;

void find_node(struct node *head,int sum)
{
	if(head == NULL)
	{
		return;
	}
	find_node(head->left,sum);
	if(Nested_find_node(temp,(sum-(head->data))) == SUCCESS)
	{
		Printf("The Second Node of Pair%d",head->data);
		return;
	}
	
	find_node(head->left,sum);
}

int Nested_find_node(struct node *head,int X)
{
	if(head == NULL)
	{
		return;
	}
	Nested_find_node(head->left,X);
	if(head->data == X)
	{
		Printf("The First Node of Pair%d",head->data);
		return SUCCESS;
	}
	Nested_find_node(head->left,X);

}

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 ...

- csgeeg January 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nitin Gupta January 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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..

- csgeeg January 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- aka January 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

after your post.

- set February 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- set February 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- 111 January 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice logic though.

- Zagoritt January 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
        }
    };
}

- Pest February 03, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More