CareerCup

Convert the bst to a sorted doubly linked list. Now place two pointers at the start and at the end of the linked list. Find the sum of the values pointed by the pointers. If the sum is greater than the required one move the pointer at the head to the previous and if the sum is less than move the pointer at the head to the next. Repeat the process and u'll get the two no's if they exists. No extra space is required and it will take O(n).

The only constraint in it is that the structure of the tree will get changed.

Flawless code... Enjoy!!!
Time O(n) ... Space(1)
----------------------------------
Keep two pointers, one at lower end another at higher end ... similar when doing it for sorted array.
----------------------------------
I am using stack for simplicity of the algorithm, but you can use Morris traversal to achieve Space(1)... If you are not able to figure out to do it with Morris traversal, then let me know. I can provide the code for that too... but that would be a bit complex to understand... so better right your own :) ....

Here we go..... CHEERS!!!

void findPair(node* root, int sum, int &a, int &b)
{
	a = -1;
	b = -1;
	// Base case '0' or '1' node in tree.
	if((!root) || (!root->left && !root->right))
		return;
	node* n1 = root, *n2 = root;
	stack<node*> p,q;
	while(true)
	{
		if(n1)
		{
			p.push(n1);
			n1 = n1->left;
		}
		else if(n2)
		{
			q.push(n2);
			n2 = n2->right;
		}
		else if(!p.empty() && !q.empty())
		{
			n1 = p.top();
			n2 = q.top();
			// tree is already traversed
			if(n1->data > n2->data) 
				return;			
			int cur_sum = n1->data + n2->data;
			if(cur_sum == sum)
			{
				// found desired numbers
				a = n1->data;
				b = n2->data;
				return;
			}
			else if(cur_sum < sum)
			{
				// move in forward direction
				p.pop();
				n1 = n1->right;
				n2 = NULL;
			}
			else
			{
				// move in backward direction
				q.pop();
				n2 = n2->left;
				n1 = NULL;
			}
		}
		else
			return;
	}
}

We can combine an in-order traversal and post-order traversal together to solve this problem. It should be a O(n).
(1) Put a cursor to the very left and another one to the very right
(2) check the sum one by one,
(3) if sum == K, print it,
(4) if sum < K, left = left->next;
(5) if sum > k, right = right->next.

This is a very heavy question for phone interview. Maybe the interviewer just want to c if you can get a clue on how to find out this, or find out how many ways you can use to sort out this problem. It is too hard to do a perfect coding in that 20 min. I put some code together here, It is not tested, not in recursive style, but I put all sub-logic into functions to make sure it is easy to read.

The code uses two stacks to record backtracking steps, which consumes constant space as required.

/*
Given a binary search tree of n nodes, find two nodes whose sum is equal to a given number k in O(n) time and constant space
*/
Stack<treenode*> stackLeft = new Stack<treenode*> ();
Stack<treenode*> stackRight = new Stack<treenode*> ();

void PrintSum(treenode* root, int sum)
{
    if(root == null)
        return;
    
    //clean up stacks
    stackLeft.clear();
    stackRight.clear();
    
    //move left cursor to the very left
    InitLeftStack(root);
    treenode* left = GetNextLeft();

    //move the right cursor to the very right
    InitRightStack(root);
    treenode* right = GetNextRight();

    while(left != null && right != null && left != right)
    {
        int localSum = left->data + right->data;

        if(localSum == sum)
        {
            cout << left->data << " " << right->data;
            left = GetNextLeft();
        }
        else if(localSum < sum)
        {
            left = GetNextLeft();
        }
        else
        {
            right = GetNextRight();
        }
    }
}

void InitLeftStack(treenode *root)
{
    treenode* cur = root;
    
    while(true)
    {
        if(cur)
        {
            stackLeft->push(cur);
            cur = cur->left;
        }
        else
            break;
    }
}

treenode* GetNextLeft()
{
    if(stackLeft == null)
        return null;
    
    treenode* ret = stackLeft->pop();
    
    InitLeftStack(ret->right);
    
    return ret;
}

void InitRightStack(treenode *root)
{
    treenode* cur = root;
    
    while(true)
    {
        if(cur)
        {
            stackRight->push(cur);
            cur = cur->right;
        }
        else
            break;
    }
}

treenode* GetNextRight()
{
    if(stackRight == null)
        return null;
    
    treenode* ret = stackRight->pop();
    
    InitRightStack(ret->left);
    
    return ret;
}

(

Can we assume that the binary search tree is stored in an array? If that is so, then we can simply apply Knade's algorithm to do this O(n) time, which works like this:

1. Put a pointer at first node and another pointer at last node.
2. If the sum of the nodes on the two pointers is equal to k, then those are your two nodes.
3. If sum is less, then, increment lower pointer.
4. If sum is more, then decrement higher pointer.

Use Knade's algo

Store leftmost leaf's value in s0 and root in s1. if s0 + s1 < sum go to parent of leftmost leaf, else go towards root's child.

You need to use recursion.

Something like that, shouldn;t be hard to implement

first subtract the root->data from sum and make the root as a first node,

then search left as well as right subtree for the second node with rest of the sum.

if we are able to get the second node then we are done
other wise look for the sum in left subtree as well as right subtree.recursively


The complexity will be O(n^2)

but there is no need for extra space to store inorder.

Convert bst to Dll

If at all we have to use o(n) space DS, then copnverting to DLL is a better solution. If you are not concerned about altering the tree then we can acheive it in o(1) spcae. Otherwise clone the tree and then convert to DLL in o(n) space

Since inorder would anyway take O(n), it doesn't matter how we implement it. It can be done iteratively as well. The solution is to move inorder from left and from right in a single parse.

#include <stdio.h>
#include <stdlib.h>

typedef struct __TreeNode__ {
	int data;
	struct __TreeNode__* parent;
	struct __TreeNode__* left;
	struct __TreeNode__* right;
} TreeNode;

void insert_into_BST(TreeNode** root, int data) {
	if (*root == NULL) {
		*root = calloc(1, sizeof(TreeNode));
		(*root)->data = data;
	} else {
		TreeNode* trav = *root;
		TreeNode* newNode = calloc(1, sizeof(TreeNode));
		newNode->data = data;
		while (trav != NULL) {
			if (data < trav->data) {
				if (trav->left == NULL) {
					newNode->parent = trav;
					trav->left = newNode;
					break;
				}
				trav = trav->left;	
			} else {
				if (trav->right == NULL) {
					newNode->parent = trav;
					trav->right = newNode;
					break;
				}
				trav = trav->right;
			}
		}
	}
}

void insert_array_into_BST(TreeNode** root, int* array, int count) {
	int ii = 0;
	for (; ii < count; ii++) {
		insert_into_BST(root, array[ii]);
	}
}

void delete_tree(TreeNode* root) {
	if (root == NULL)
		return;
	delete_tree(root->left);
	delete_tree(root->right);
	free(root);
}

TreeNode* find_smallest(TreeNode* root) {
	while (root->left) {
		root = root->left;
	}
	return root;
}

TreeNode* find_largest(TreeNode* root) {
	while (root->right) {
		root = root->right;
	}
	return root;
}

TreeNode* find_predecessor(TreeNode* root) {
	if(root->left) {
		root = root->left;
		while (root->right) {
			root = root->right;
		}
		return root;
	} else if( root == root->parent->right) {
		return root->parent;
	} else {
		while( root == root->parent->left)
			root = root->parent;
		return root->parent;
	}
	
	return NULL;
}

TreeNode* find_successor(TreeNode* root) {
	if(root->right) {
		root = root->right;
		while (root->left) {
			root = root->left;
		}
		return root;
	} else if( root == root->parent->left) {
		return root->parent;
	} else {
		while( root == root->parent->right)
			root = root->parent;
		return root->parent;
	}
	
	return NULL;
}

void print_pairs_with_sum(TreeNode* root, int sum) {
	TreeNode* smallest = find_smallest(root);
	TreeNode* largest = find_largest(root);
	
	if (smallest->data + find_successor(smallest)->data > sum ||
		largest->data + find_predecessor(largest)->data < sum) {
			printf("No elements found...\n");
		}
	
	while( smallest->data < largest->data) {
		if (sum == (smallest->data + largest->data)) {
			printf("%d %d\n", smallest->data, largest->data);
		}
		smallest = find_successor(smallest);
		while( smallest->data + largest->data > sum) {
			largest = find_predecessor(largest);
		}
	}
	
}

int main() {
	
	TreeNode* root = NULL;
	int array[11] = {10,7,3,8,1,4,12,11,16,14,19};
	insert_array_into_BST(&root,array,11);
	print_pairs_with_sum(root,16);
	delete_tree(root);
	return 0;
}

Hey guyz, How about this algorithm... I wrote the recursive Code logic here....

boolean findNodesofSum( Node refer1, Node refer2, int sum ){
	// initially refer1 and refer2 are references to the root of the bst
	
	if(refer1.value + refer2.value > sum){
		if(findNodeofSum(refer1.right, refer2, sum))
			return true;
		if(findNodeofSum(refer1, refer2.right, sum))
			return true;
		
	}
	
	if(refer1.value + refer2.value < sum){
		if(findNodeofSum(refer1.left, refer2, sum))
			return true;
		if(findNodeofSum(refer1, refer2.left, sum))
			return true;
	
	}

	if(refer1.value + refer2.value == sum){
		print("The desired value is achieved by the sum of"+ refer1.value + " + " + refer2.value);
		return true;
	}
	
	return false;
}

The nodes can be achieved in O(n) time as in the worst case we'll be touching all the nodes in the tree once.

public static void findNodes(TreeNode node, int sum) {
		List<TreeNode> l = new LinkedList<TreeNode>();
		convertIntoList(node, l);
		int i = 0;
		int j = l.size()-1;

		while (i < j) {
			if (l.get(i).data + l.get(j).data == sum) {
				System.out.println("nodes are: " + l.get(i).data + ", and "
						+ l.get(j).data);
				i++;
				j--;
			} else if (l.get(i).data + l.get(j).data < sum) {
				i++;
			} else {
				j--;
			}
		}
	}

	public static void convertIntoList(TreeNode node, List<TreeNode> l) {
		if (node == null) {
			return;
		} else {
			convertIntoList(node.left, l);
			l.add(node);
			convertIntoList(node.right, l);
		}
	}

void findNodes(Node * root,int sum)
{
	if(!root) return;
	findSum(root,root,sum);
}
void findSum(Node * leftEnd,Node * rightEnd,int sum,bool &result)
{
	if(!result && leftEnd->left && rightEnd->right)
		findSum(leftEnd->left,rightEnd->right,sum,result);		
	else if(!result && leftEnd->left)
		findSum(leftEnd->left,rightEnd,sum,result);
	else if(!result && rightEnd->right)
		findSum(leftEnd,rightEnd->right,sum,result);
	if(leftEnd->data  + rightEnd->data == sum)
	{
		cout << "The values that equal to the given sum are:" << leftEnd->data << " " << rightEnd->data << endl;
		result = true;
	}
	if(!result && leftEnd->right && rightEnd->left)
		findSum(leftEnd->right,rightEnd->left,sum,result);		
	else if(!result && leftEnd->right)
		findSum(leftEnd->right,rightEnd,sum,result);
	else if(!result && rightEnd->left)
		findSum(leftEnd,rightEnd->left,sum,result);
}

Let me know the feedback about the above code.

From geeksforgeeks(dot)org(slash)find-a-pair-with-given-sum-in-bst

/* In a balanced binary search tree isPairPresent two element which sums to
       a given value time O(n) space O(logn) */
    #include <stdio.h>
    #include <stdlib.h>
    #define MAX_SIZE 100
    
    // A BST node
    struct node
    {
        int val;
        struct node *left, *right;
    };
    
    // Stack type
    struct Stack
    {
        int size;
        int top;
        struct node* *array;
    };
    
    // A utility function to create a stack of given size
    struct Stack* createStack(int size)
    {
        struct Stack* stack =
            (struct Stack*) malloc(sizeof(struct Stack));
        stack->size = size;
        stack->top = -1;
        stack->array =
            (struct node**) malloc(stack->size * sizeof(struct node*));
        return stack;
    }
    
    // BASIC OPERATIONS OF STACK
    int isFull(struct Stack* stack)
    {   return stack->top - 1 == stack->size;  }
    
    int isEmpty(struct Stack* stack)
    {   return stack->top == -1;   }
    
    void push(struct Stack* stack, struct node* node)
    {
        if (isFull(stack))
            return;
        stack->array[++stack->top] = node;
    }
    
    struct node* pop(struct Stack* stack)
    {
        if (isEmpty(stack))
            return NULL;
        return stack->array[stack->top--];
    }
    
    // Returns true if a pair with target sum exists in BST, otherwise false
    bool isPairPresent(struct node *root, int target)
    {
        // Create two stacks. s1 is used for normal inorder traversal
        // and s2 is used for reverse inorder traversal
        struct Stack* s1 = createStack(MAX_SIZE);
        struct Stack* s2 = createStack(MAX_SIZE);
    
        // Note the sizes of stacks is MAX_SIZE, we can find the tree size and
        // fix stack size as O(Logn) for balanced trees like AVL and Red Black
        // tree. We have used MAX_SIZE to keep the code simple
    
        // done1, val1 and curr1 are used for normal inorder traversal using s1
        // done2, val2 and curr2 are used for reverse inorder traversal using s2
        bool done1 = false, done2 = false;
        int val1 = 0, val2 = 0;
        struct node *curr1 = root, *curr2 = root;
    
        // The loop will break when we either find a pair or one of the two
        // traversals is complete
        while (1)
        {
            // Find next node in normal Inorder traversal. See following post
            while (done1 == false)
            {
                if (curr1 != NULL)
                {
                    push(s1, curr1);
                    curr1 = curr1->left;
                }
                else
                {
                    if (isEmpty(s1))
                        done1 = 1;
                    else
                    {
                        curr1 = pop(s1);
                        val1 = curr1->val;
                        curr1 = curr1->right;
                        done1 = 1;
                    }
                }
            }
    
            // Find next node in REVERSE Inorder traversal. The only
            // difference between above and below loop is, in below loop
            // right subtree is traversed before left subtree
            while (done2 == false)
            {
                if (curr2 != NULL)
                {
                    push(s2, curr2);
                    curr2 = curr2->right;
                }
                else
                {
                    if (isEmpty(s2))
                        done2 = 1;
                    else
                    {
                        curr2 = pop(s2);
                        val2 = curr2->val;
                        curr2 = curr2->left;
                        done2 = 1;
                    }
                }
            }
    
            // If we find a pair, then print the pair and return. The first
            // condition makes sure that two same values are not added
            if ((val1 != val2) && (val1 + val2) == target)
            {
                printf("\n Pair Found: %d + %d = %d\n", val1, val2, target);
                return true;
            }
    
            // If sum of current values is smaller, then move to next node in
            // normal inorder traversal
            else if ((val1 + val2) < target)
                done1 = false;
    
            // If sum of current values is greater, then move to next node in
            // reverse inorder traversal
            else if ((val1 + val2) > target)
                done2 = false;
    
            // If any of the inorder traversals is over, then there is no pair
            // so return false
            if (val1 >= val2)
                return false;
        }
    }
    
    // A utility function to create BST node
    struct node * NewNode(int val)
    {
        struct node *tmp = (struct node *)malloc(sizeof(struct node));
        tmp->val = val;
        tmp->right = tmp->left =NULL;
        return tmp;
    }
    
    // Driver program to test above functions
    int main()
    {
        /*
                       15
                    /     \
                  10      20
                 / \     /  \
                8  12   16  25    */
        struct node *root =  NewNode(15);
        root->left = NewNode(10);
        root->right = NewNode(20);
        root->left->left = NewNode(8);
        root->left->right = NewNode(12);
        root->right->left = NewNode(16);
        root->right->right = NewNode(25);
    
        int target = 28;
        if (isPairPresent(root, target) == false)
            printf("\n No such values are found\n");
    
        getchar();
        return 0;
    }

Here i am pasting recursion code. My thoughts are as below:
1) If sum is less than root then both the numbers will be left of the BST without root.
2) If sum is equals to the root then numbers will be at the root including root.
3) If sum is greater than root then there are 3 cases: a) Both are at right side b) Both at left side c) One is in left side and other is at side.

After this decision we subtract the node value with the given sum and check whether the difference value present or not. Here is working code:

private Integer sum(LeftLeaningRedBlackTree<Integer, Integer>.Node node,
			Integer number) {
		if (node == null) {
			return null;
		}

		int cmp = number.compareTo(node.key);
		int nodeInt = node.key.intValue();
		int userInt = number.intValue();

		if (cmp < 0) {
			if (node.left == null) {
				return null;
			}
			nodeInt = node.left.key.intValue();

			int diff = nodeInt - userInt;
			Integer found = rbt.search(node.left, diff);
			if (found == null) {
				return sum(node.left, number);
			} else {
				System.out.println(nodeInt + " " + diff);
				return 0;
			}
		} else if (cmp > 0) {
			int diff = userInt - nodeInt;
			boolean found = rbt.search(diff);
			if (!found || diff == nodeInt) {
				return sum(node.right, number);
			} else {
				System.out.println(nodeInt + " " + diff);
				return 0;
			}
		} else {
			int diff = userInt - nodeInt;
			boolean found = rbt.search(diff);
			if (!found) {
				return sum(node.right, number);
			} else {
				System.out.println(nodeInt + " " + diff);
				return 0;
			}
		}
	}

Search(tree,sum)
{
for each node N of tree
{
sum1=sum-N->data;
if((N2=BinarySearch(Tree,sum1) )) //if second node exist
{
N1=N;
return N1 and N2;
}
}

Return 0//no such node
}



complexity(Nlogn)