CareerCup

Use stack to simulate inorder traversal of a tree. The rest is simply the linear time 2 sum algorithm. This however, means that you will have to use some extra space to store stack.

class InorderIterator{
	TreeNode *root;
	stack<TreeNode*> node_stack;
	stack<int> state_stack;
public:
	InorderIterator(TreeNode *ptr):
	root(ptr){
		node_stack.push(root);
		state_stack.push(0);
		
		TreeNode *node;
		int state;
		while(!node_stack.empty()){
			node = node_stack.top();
			node_stack.pop();
			
			state = state_stack.top();
			state_stack.pop();
			
			if(state==0){
				node_stack.push(node);
				state_stack.push(1);
				if(node->left!=NULL){
					node_stack.push(node->left);
					state_stack.push(0);
				}
			}else{
				node_stack.push(node);
				state_stack.push(1);
				break;
			}
		}
	}
	TreeNode* get_node(){
		return node_stack.empty() ? NULL : node_stack.top();
	}
	void proceed(){
		if(state_stack.empty()){
			return;
		}
		TreeNode *node;
		int state;
		
		while(true){
			node = node_stack.top();
			node_stack.pop();
		
			state = state_stack.top();
			state_stack.pop();
			
			if(state==0){
				node_stack.push(node);
				state_stack.push(1);
				if(node->left!=NULL){
					node_stack.push(node->left);
					state_stack.push(0);
				}
			}else{
				if(node->right!=NULL){
					node_stack.push(node->right);
					state_stack.push(0);
				}
			}
			if(state_stack.top()==1){
				break;
			}
		}
	}
};

Another idea is to first in-place convert BST to Doubly Linked List (DLL), then find pair in sorted DLL in O(n) time. This solution takes O(n) time and O(Logn) extra space, but it modifies the given BST. Refernce : [www] .geeksforgeeks.org/find-if-there-is-a-triplet-in-bst-that-adds-to-0/

Here is an idea (using a recursion, but may be rewritten using stack like someone mentioned above). Still uses extra memory though.

Different traverser will return different nodes, if there is more than one pair.

//Implementation of traverser that traverses tree in pre order manner and collects data.
//Traversal is only happening while data collector hasn't collected all the data it needs.   
public class PreOrderTraverser implements Traverser<TreeNode>{
	@Override
	public void traverse(TreeNode rootNode,DataCollector<TreeNode, ?> dataCollector) throws Exception {
		if(dataCollector==null || rootNode == null)
			throw new Exception("Must provide both - rootNode and dataCollector");

		if(!dataCollector.dataCollected()){
			if(rootNode.getLeftNode() != null){
				traverse(rootNode.getLeftNode(),dataCollector);
			}
		}
			
		if(!dataCollector.dataCollected()){
				if(rootNode.getRigthNode() != null){
					traverse(rootNode.getRigthNode(),dataCollector);
				}			
		}
	}	
}

public class SumValueCollector implements DataCollector<TreeNode,Integer[]>{
			private Set<Integer> values = new HashSet<Integer>(); 
			private int totalSum = 0;
			private Integer[] nodeValuePair= {0,0};
			
			public void setSumToLookfor(int sum){
				totalSum = sum;
			}
			
			@Override
			public void collect(TreeNode searchContext) {
				if(values.contains(totalSum - searchContext.getValue())){
					nodeValuePair[0]=totalSum - searchContext.getValue();
					nodeValuePair[1]=searchContext.getValue();
				}else{
					values.add(searchContext.getValue());
				}
			}

			@Override
			public boolean dataCollected() {
				return (nodeValuePair[0]!=0 && nodeValuePair[1]!=0);
			}

			@Override
			public Integer[] getResult() {
				return nodeValuePair;
			}
	}

Test:
Traverser<TreeNode> preOrderTraverser = new PreOrderTraverser();
		SumValueCollector sumChecker = new SumValueCollector();
		sumChecker.setSumToLookfor(10);//sum of two nodes
		preOrderTraverser.traverse(value7, 

		System.out.println("tree contains x an y nodes where x+y=10:" + sumChecker.dataCollected());
		if (sumChecker.dataCollected())
				System.out.println("node values:" + sumChecker.getResult()[0]+" and "+sumChecker.getResult()[1]);

travel to the smallest value, a. Look for x-a. If it's there, done. If not, call the entry where it should be b. You can go from a to the next smallest value and now call that a. As long as a+b<x, go to next choice for a. Once a+b >=x, if =, then done. If >, then start decreasing b as you did a until a+b<=x. Now go back to a. Continue until a=b.

int data ; 
struct node *left; 
strcut node *right;
}

struct node *root;  
//Search always starts with root.  Because sum - temp->data can be found anywhere in the tree. 

find_num( struct node *temp , int sum)
{
      
       if (!temp) 
            return; 
       ret_val = search_bst(root, sum - temp->data); 
       if(ret_val == true ) // number found 
       { 
                 printf (" Numbers are %d  %d " , sum-temp->data , temp ->data); 
       }
      
       find_num(temp->left , sum); 
       find_num(temp->right, sum);
}


Search_bst is generic function which returns true or false based on search result.

Another O(nlogn) solution without extra space can be
foreach(element e in BST)
search(x-e, BST);

I would do a double inorder traversal. In my first inorder traversal I would pick up a node. I would do a difference with the sum to find the node that I need to look for in the second traversal. If the second traversal finds it then yes the sum exists.

public boolean hasSummationNodes(Node node, int sum) {
		boolean found = inorderFirstNode(node, sum);
		return found;
	}

	public boolean inorderFirstNode(Node node, int sum) {
		if (node == null) {
			return false;
		}
		boolean foundLeft = inorderFirstNode(node.leftChild, sum);
		int value = sum - node.data;
		boolean found = inorderSecondNode(root, value);
		boolean foundRight = inorderFirstNode(node.rightChild, sum);
		return found | foundLeft | foundRight;
	}

	public boolean inorderSecondNode(Node node, int value) {
		boolean found = false;
		
		if (node == null) {
			return false;
		}
		
		boolean foundLeft = inorderSecondNode(node.leftChild, value);
		if (node.data == value) {
			found = true;
			System.out.println(node.data);
		}
		boolean foundRight = inorderSecondNode(node.rightChild, value);
		return found | foundLeft | foundRight;
	}

Since no extra space is allowed, I did an inorder traversal to find the first node. Substracted that from the sum to determine the expected value for the second node. This I then passed to another method that does an inorder traversal to find the second node. If the second node is found then yes a sum exists. Efficiency is O(n2).

public boolean hasSummationNodes(Node node, int sum) {
		return inorderFirstNode(node, sum);
	}

	public boolean inorderFirstNode(Node node, int sum) {
		if (node == null) {
			return false;
		}
		boolean foundLeft = inorderFirstNode(node.leftChild, sum);
		int value = sum - node.data;
		boolean found = inorderSecondNode(root, value);
		boolean foundRight = inorderFirstNode(node.rightChild, sum);
		return found | foundLeft | foundRight;
	}

	public boolean inorderSecondNode(Node node, int value) {
		boolean found = false;
		
		if (node == null) {
			return false;
		}
		
		boolean foundLeft = inorderSecondNode(node.leftChild, value);
		if (node.data == value) {
			found = true;
		}
		boolean foundRight = inorderSecondNode(node.rightChild, value);
		return found | foundLeft | foundRight;
	}