google-code-prettify

Tuesday, 28 May 2013

Binary Tree - sum of two nodes (Google Interview Question)

Here is another Google Interview problem:
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.
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.

void algorithm(Stack stk1, 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.

3 comments:

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

    ReplyDelete
    Replies
    1. Yes, 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.

      Delete
  2. This comment has been removed by a blog administrator.

    ReplyDelete