CareerCup

Should be simple...Convert the tree into a doubly linked list and then find the required two nodes by placing a pointer in the front and one at the end.....

BST data structure supports the operations of Min, Max, Predecessor and Successor. Just like in a sorted array we increment the pointer from min value and decrement the pointer from max value to check the sum, we repeatedly use the pointers returned by Successor and Predecessor functions in a BST to check the sum.

You have parent pointer at the tree structure to facilitate iterative traversal. You can also modify the tree temporarily if use Morris traversal.

I think we can use inorder traversal with recursion and the store it in an array (that will be sorted ). Will it work ??

public static void sumSearch(Node nd1, Node nd2, sum){
    if(nd2 == null){
        search sum - nd1 in tree nd1;
        if (found)
          print;
        else{
            searchSum(nd1.left, nd1.right, sum);
        }
    }
    if(nd1 == null){
        search sum - nd2 in tree nd2;
        if (found)
          print;
        else{
            searchSum(nd2.left, nd2.right, sum);
        }
    }
	
	if(nd1 + nd2 > sum){
	    sumsearch(nd1.left, nd2);
	    sumsearch(nd1, nd2.left);
	} else if(nd1 + nd2 == sum){
	    print
	} else {
	    sumSearch(nd1.right, nd2);
	    sumSearch(nd1, nd2.right);
	}
    
}

I am doubting if timeO(n) is possile

I think this question is equivalent to the finding of two values in a sorted array that sum to some value.

Travesre the Tree in Inorder and store the elements and the corresponding pointers to nodes in a tree in an array in O(n) time........Then the code as follows

void fun(int arr[,int sum,int *a,int*b)
for(int i=0;i<n;i++)
for(int j=i;j<n;j++)
{
      if(a[i]+a[j]==sum) 
       {
          *a=i;
           *b=j;
           exit(0);
          }
  }

@krishna : Can u please post the correct solution in O(n) time and O(1) space pls....

This problem can be reduced to finding the sum on a sorted array (I'll get back to the tree in a sec). For this part, we use 2 pointers one at the start and one at the end, evaluate the sum and adjust accordingly (increment the lower pointer to add or decrement the higher pointer to substract) until the result is found or the pointers meet.

How do we achieve the same traversal on a tree? Use inorder for the lower pointer and a "reverse" inorder (right -> root -> left) for the higher one. If recursion is not allowed then use the Morris algorithm.

I tried the Chong Ovalle's solution in Java, I have something that's working, I just check if the sum is equal to 19 and stop the recursion, but I don't know about the complexity. Could anyone give me some feedback?

boolean found = false;
public void inOrderDouble(Node root_left, Node root_right, boolean leftRec){
if(root_left==null && leftRec) return;
if(leftRec)
inOrderDouble(root_left.left,root_right,true);


if(root_right==null && !leftRec) return;

inOrderDouble(root_left,root_right.right, false);



if(root_left.value + root_right.value == 19){
System.out.println(root_left.value + " "+ root_right.value);
found = true;

}
if(!found)
inOrderDouble(root_left,root_right.left, false);
if(!found)
inOrderDouble(root_left.right,root_right, true);
}

Hi Guys , I converted BDT in to Sorted DLL (it will take o(n) time & O(1) space) then find the two nodes in DLL which equals to given number
shashank7s dot blogspot dot com/2011/06/wap-to-find-two-nodes-into-binary dot html
let me know if anything wrong ,you can comment

Shashank

sfmkflsdkf

People are looking for a reliable/valuable answers. Please don’t give shit answers. If you really don’t know then keep silent and read.
Kind request.

great Logic by sashank

Step 1: Do Inorder traversal in O(n) to convert to array which will be sorted since it is BST.

Step 2 :: Use the sorted array:: Code in C#

class Program
{
static void Main(string[] args)
{
int[] a = new int[] {1,2,3,5,6,8,10,13,14,15,18,20,29,30};
OutputNode o = Search2BSTNode(a, 0, a.Length - 1,29);
if (o == null)
{
Debug.WriteLine("Value not found");
return;
}
Debug.WriteLine(String.Format(" start:{0} value:: {1} end: {2} value:: {3}",o.StartIndex,o.StartValue,o.EndIndex,o.EndValue));
}

private static OutputNode Search2BSTNode(int[] a, int start, int end, int k)
{
int mid = (start + end)/2;
int x = a[start], y = a[mid];
if( (x + y) == k)
{
if (start == mid) return null; //Because only one value is found.
return new OutputNode(start,x,mid,y); //Good
}
if (start < end)
{
if (y > k) // sum is less than middle element so on left half.
{
end = mid;
return Search2BSTNode(a, start, end, k);
}
if ((x + y) > k) // shift middle towards left.
{
end--;
return Search2BSTNode(a, start, end, k);
}
// (x+y) < k
{
start++; //shift middle towards right.
return Search2BSTNode(a, start, end, k);
}
}
return null;
}

public class OutputNode
{
private int _startIndex;
private int _startValue;
private int _endIndex;
private int _endValue;

public OutputNode(int startIndex, int startValue, int endIndex, int endValue)
{
_startIndex = startIndex;
_startValue = startValue;
_endIndex = endIndex;
_endValue = endValue;
}
#region Properties
public int StartIndex {get { return _startIndex; }}
public int StartValue { get { return _startValue; }}
public int EndIndex { get { return _endIndex; }}
public int EndValue { get { return _endValue; }}
#endregion

}

}

Let me know if its an issue. I tested it and it working but maybe i missed something.

- the sum should be always > the node, if not move left

void findNodes(int k , Node *r)
{

if (r == null) return;

while(r->data > sum) //
r = r->r->left;

int d = k - r ->data;

if(findSecodNode(d))

cout<< r-> data <<" "<< d;

else
{

findNodes(k,r->left);
findNodes(k,r->right);
}

}
}

//the sum should be always > the node, if not move left

void findNodes(int k , Node *r)
{

if (r == null) return;

while(r->data > k) // go to the node which is less than k
r = r->left;

int d = k - r ->data;

if(findSecodNode(d))

cout<< r-> data <<" "<< d;

else
{

findNodes(k,r->left);
findNodes(k,r->right);
}

}

Use a combination of iterative inorder traversal, reverse in-order traversal and the algorithm to find two numbers in a sorted array whose sum is k

I am also treating the tree as a sorted array, but I find it difficult (if not impossible) to simulate pointing to the first & last node, then advancing either pointer recursively. Note that I am assuming we don't have a parent pointer for each node, otherwise it would be easier. So instead of starting off with first & last node, I am going to start off with the middle 2 nodes instead. The root is one of them, and I will try using both its left & right children as the other "middle" node. Hence the 2 calls in findNodes().

Idea is to recursively compare the current sum with K. If current sum is equal, we found the 2 nodes. If current sum < K, we can increase the sum by trying with the right child of either node. Similarly if current sum > K.

I haven't proved that starting from the middle will work, but I did test my code against several cases and got the right answers so far. This solution is O(n) time and O(1) space. It can be further optimized by avoiding having to call findNodes() twice, but that would still be O(n).

static Node[] findNodes(Node n, int K) {
	Node[] result = findHelper(n.left, n, K);
	if(result != null)
		return result;
	else return findHelper(n, n.right, K);
}

static Node[] findHelper(Node left, Node right, int K) {
	if(left == null || right == null || left == right)
		return null;
	if(left.value + right.value == K) {
		Node[] result = new Node[2];
		result[0] = left;
		result[1] = right;
		return result;
	} else if(left.value + right.value < K) {
		Node[] result = findHelper(left.right, right, K);
		if(result != null)
			return result;
		else return findHelper(left, right.right, K);
	} else {
		Node[] result = findHelper(left.left, right, K);
		if(result != null)
			return result;
		else return findHelper(left, right.left, K);
	}
}

firstly compute the k=sum-root element now find this k element in tree...