## Ibibo Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**In-Person

@Artist,

Good approach.I have a question though:

Worst case scenario (lets say the right most leaf and its parent form the sum), you will traverse the whole tree and search the whole tree for val correct? which would make it O(n^2) ?

My implementation of your algorithm ...

```
struct Node
{
int data;
Node* left;
Node* right;
}
```

Driver Function

```
bool FindSum(Node* root, int sum, Node* node1, Node* node2)
{
node1 = NULL;
node2 = NULL;
if(!root)
return false;
Node* current = root;
while(current && current->data > sum)
current = current->left;
if(!current)
return false;
FindSum(current, current, sum, node1, node2);
if(!node1)
return false;
return true;
}
```

Recursive Function to do a In-Order traversal

```
void FindSum(Node* root, Node* current, int sum, Node* node1, Node* node2)
{
int value = sum - current->data;
if(FindNode(root, value, node2))
{
node1 = current;
return;
}
if(current->left)
FindSum(root, current->left, sum, node1, node2);
if(current->right)
FindSum(root, current->right, sum, node1, node2);
}
```

Helper Function to find a node with given data

```
bool FindNode(Node* root, int data, Node* node)
{
if(!root)
return false;
while(root)
{
if(root->data == data)
{
node = root;
return true;
}
else if(root->data < data)
root = root->right;
else
root = root->left;
}
return false;
}
```

To come up with (one of) the best possible solution to this problem, we need to be aware of the limitations and inherent advantages of using a BST. The problem can then be solved efficiently. Let us take a look at (some of) the properties of BST and the nature of the problem that’ll help us in finding a solution that is very close to the best possible solution.

1. In a BST, the numbers are sorted in a particular order during insertion. For any given node at any level, the value of the nodes in its left sub tree are always lesser than the value of the parent node and the value of the nodes in the right sub tree are always greater than the value of the parent node.

2. There are no nodes with duplicate values in a BST.

3. We have to eliminate (or don’t have to find) duplicate pairs.

Step 1. We first find (zero-in on) the node whose value is less than the given number n. We call this node newRoot (the logic behind this move is if we hope to find all pairs of numbers that add up to n in a BST, we should ignore the nodes that are greater or equal to n. Refer to point 1 above and this reasoning will seem obvious).

Step 2. Start with the node that was identified in step 1.

a. If the value of this node is less than n/2 then search for the node starting from newRoot with the value n – value (the logic is to limit the value for ki, our first number in the pair. If we find ki, kj must be out there).

b. If a node was found that satisfied the search condition in step 2a, print the pair [value, n – value] (we found kj using ki).

Step 3. Repeat step 2 for the current node’s left child.

Step 4. If the value of the current node is less than n/2, repeat step 2 for current node’s right child (there is no point looking for a number on the right side of the current node if the node’s value is greater than n/2 since we know we won’t find it).

what if node value is negative? then there could be no node value less than the given number n!

O(n) solution without using any extra or auxiliary space-

1. Find the left most node of tree means the

smallest one. Worst case complexity O(n).

2 . similarly find the right most node, say both to be a and b respectively.

3. Now traverse the tree recursively from left node to right as well right to left simultaneously in inorder form. Terminating condition would be when a->val>b->val or either we get the required sum.

My approach would be:

1. traverse the tree in Inorder traversal - while scanning, store the elements in a array.

2. Scan the array using two forloops and find the elements that sum to required sum.

Tried not using an array for this, but havent come up to a soln yet.

Thanks

not a good solution...has O(n^2 complexity)...you need to take advantage of the fact that its a BST or that the array you created after inorder traversal is sorted.

instead of two for loops we can use BST property to reduce the complexity to nlogn...

Something like this,

i = 1; j = n;

mid = (i + j)/2;

while( i < j){

value = sum - a[i];

search the array for "value" using the BST property and if found set j to this particular location(print these values) / if not found set it to the location that just greater then value.

increment i;

}

This will run O(nlogn) & space O(n).

```
smaller= bst.getMin();
while (smaller<larger){
larger=bst.floor(k-smaller);
if (larger+smaller==k){
print(larger, smaller);
return;
}
smaller=bst.ceiling(k-larger);
if (larger+smaller==k){
print(larger,smaller);
return;
}
print("no answer");
}
```

Could you please explain your answer...and also I don't recall floor and ceiling being normal functions of a bst...

It is easy to modify a Binary search to get a FLOOR or CEILING. if we you are at a leaf and have not found the key, return predecessor or successor, respectively.

1- choose the min as for the smaller.

2- find the larger number in a way that smaller+larger is equal to k or is closet smaller number to k. return if equal to k.

3- if you are here it means that smaller + larger < k. therefore, let's find another number for smaller so that smaller + larger = k or is the closest smaller number to k. if equal to k return. else go to 2.

basically, larger variable gets smaller in each step. and smaller variable gets larger in each step, until either the result is found or smaller get bigger than larger.

You could store the nodes into a hastable with extra O(n) space.

Traverse the BST.

If node.value>k, visit only the left child of the node.

Else if n-k<n: check to see if n-k is in the hastable if not, put n into the hastable, visit the left child first, the the right.

Else: check to see if n-k is in the hashtable if not put n into visit right child first, then visit left child.

//of course in both else scenarios, if n-k is in the hashtable, you have found a pair and you can exit.

Runtime: this will be at most O(n) but it should be in practice ~O(lgn).

using System;

using System.Collections.Generic;

using System.Text;

namespace bst

{

public class Node

{

private int value;

private Node left;

private Node right;

public Node(int value, Node left, Node right)

{

this.value = value;

this.left = left;

this.right = right;

}

public int Value

{

get { return this.value; }

}

public Node Left

{

get { return this.left; }

}

public Node Right

{

get { return this.right; }

}

public override string ToString()

{

return value.ToString();

}

}

public class TwoNumbers

{

public int No1 { get; set; }

public int No2 { get; set; }

}

public class Tree

{

public TwoNumbers SumOfTwo(Node root, int value)

{

Node temp = null;

TwoNumbers ret = new TwoNumbers();

temp = root;

while (temp != null)

{

Console.WriteLine(temp);

if (value > temp.Value)

{

if (ret.No1 == 0)

{

if (temp.Right == null || temp.Right.Value >= value)

{

Console.WriteLine("No1 set to " + temp);

ret.No1 = temp.Value;

temp = root;

continue;

}

else

{

temp = temp.Right;

continue;

}

}

else

{

if (value - ret.No1 == temp.Value && ret.No1 != temp.Value)

{

Console.WriteLine("No2 set to " + temp);

ret.No2 = temp.Value;

return ret;

}

if (value - ret.No1 < temp.Value)

{

temp = temp.Left;

}

else

{

temp = temp.Right;

}

}

}

else

{

temp = temp.Left;

}

}

return ret;

}

}

class Program

{

static Node PrepareBinaryTree()

{

Node n1 = new Node(1, null, null);

Node n4 = new Node(4, null, null);

Node n7 = new Node(7, null, null);

Node n13 = new Node(13, null, null);

Node n2 = new Node(2, n1, null);

Node n6 = new Node(6, n4, n7);

Node n14 = new Node(14, n13, null);

Node n3 = new Node(3, n2, n6);

Node n10 = new Node(10, null, n14);

Node n8 = new Node(8, n3, n10);

return n8;

}

static void Main(string[] args)

{

Tree tree = new Tree();

Node root = PrepareBinaryTree();

TwoNumbers found = tree.SumOfTwo(root, 2);

Console.ReadLine();

}

}

}

void Find(struct Node *node,int sum,map<int ,struct Node *> &mymap)

{

if(!node)

return;

map<int ,struct Node *> :: iterator it;

Find(node->left,sum,mymap);

it=mymap.find(node->data);

if(it!=mymap.end())

printf("%d %d \n",node->data,it->second->data);

else

mymap.insert(pair<int,struct Node *>(sum-node->data,node));

Find(node->right,sum,mymap);

}

Two stacks S1,S2 both have inorder traversal in LrtR and RRtL manner, keep popping out from stack and check sum.

I think if you used an array instead of a stack, you won't have to store the data twice.

here is my approach

1. store inorder traversal of the tree to a list

2. given the numbers are sorted increasing order after the inorder traversal, you can then do a linear scan.

```
// Given a BST, Find if two nodes add up to a sum K
public static bool SumExists(Node node, int k)
{
List<int> nodeValues = InOrder(node);
int left = 0, right = nodeValues.Count() - 1;
while(left < right)
{
int val = nodeValues[left] + nodeValues[right];
if (val == k)
return true;
else if (val < k)
left ++;
else
right --;
}
return false;
}
List<int> InOrder(Node root)
{
List<int> output = new List<int>();
InOrder(root, output);
return output;
}
void InOrder(Node root, List<int> output)
{
if(root == null)
return;
InOrder(root.left, output);
output.add(root.val);
InOrder(root.right, output);
}
```

a simple nlogn solution will be do a inorder traversal of the tree...at every node calculate val = node.value - k(given number) and do a binary search for val from the root node if node.value < val or from the current node if node.value > val

- The Artist December 14, 2012we can initially find out the max and min values in the tree to increase the efficiency further by using the max or min value to identify whether its worth going to the left or right child of a given node