The solution uses two stacks and the size of the binary tree. The approach is recursive and is similar to the binary search algorithm in arrays. The two stacks contain candidate answer numbers and on each iteration based on a calculation we pop or add new number in a stack. The binary tree size is used in cases where no answer exists. In these cases the algorithm starts endless loop.Given a BST and a value x. Find two nodes in the tree whose sum is equal x. Additional space: O(height of the tree). It is not allowed to modify the tree.

void algorithm(Stackstk1, Stack stk2, double x, int size) { if (size == 0){ System.out.println("No answer is found!"); return; } if (!stk1.isEmpty() && !stk2.isEmpty()) { if (stk1.peek().data + stk2.peek().data == x) { System.out.println("Nodes are:\n" + stk1.peek().data + "\n" + stk2.peek().data); return; } if (stk1.peek().data + stk2.peek().data > x) { if(stk2.size()==1){ BinaryTree node = stk2.pop(); stk2.add(node); addRightNodes(stk2, node.getLeft()); } else { addLeftNodes(stk2, stk2.pop()); } } else if (stk1.peek().data + stk2.peek().data < x) { if(stk1.size()==1){ BinaryTree node = stk1.pop(); stk1.add(node); addLeftNodes(stk1, node.getRight()); } else { addRightNodes(stk1, stk1.pop()); } } } algorithm(stk1, stk2, x, --size); }

See also the "Sum of nodes at odd and even levels of Binary Tree" problem.

Saving all the elements in an array and then scanning from two ends would be easy to implement I think.

ReplyDeleteYes, it is true. In case you don't have the restriction "Additional space: O(height of the tree)" this will be a good solution with an easy implementation.

DeleteThis comment has been removed by a blog administrator.

ReplyDelete