CareerCup

1) keep two "pointers", one PL at the leftmost and one PR at the rightmost.
2) Add the values of two nodes pointed, say SUM
3) if SUM = k, you ask for a cup of coffee nicely.
4) if SUM > k, you shift your PR to it's predecessor
5) if SUM < k, you shift your PL to it's successor
6) go back to 2) while PR != PL
7) No such two damn nodes.

JD give us very good logic for this problem on chatterous. We will covert BST to Circular Doubly LinkedList in-place.
Then normal two pointer logic
here is the logic for converting BST To DLL

private static TreeNode<Integer> bstToList(TreeNode<Integer> root) {
                // TODO Auto-generated method stub
                if (root == null)
                        return null;
                TreeNode<Integer> first = bstToList(root.left);
                TreeNode<Integer> second = bstToList(root.right);
                // Merge first with root and then root with second
 
                root.left = root;
                root.right = root;
                TreeNode<Integer> aList = append(first, root);
                aList = append(aList, second);
                return aList;
        }
 
        private static TreeNode<Integer> append(TreeNode<Integer> first,
                        TreeNode<Integer> second) {
                // TODO Auto-generated method stub
                TreeNode<Integer> l = null;
                TreeNode<Integer> r = null;
                if (first == null) {
                        if (second.left == null)
                                second.left = second;
                        if (second.right == null)
                                second.right = second;
                        return second;
                }
                if (second == null) {
                        if (first.left == null)
                                first.left = first;
                        if (first.right == null)
                                first.right = first;
                        return first;
                }
                l = first.left;
                r = second.left;
 
                l.right = second;
                second.left = l;
 
                first.left = r;
                r.right = first;
 
                return first;
        }

Full code is here ideone com/5mGIM for BST to DLL

Based on following link cslibrary stanford edu/109/TreeListRecursion html

My solution is to convert in place the BST in a DLL:

node temp = new node();
        public void bsttodll(node n)
        {
            if (n == null) return ;
           
            bsttodll(n.left);
            n.left = temp;
            temp.right = n;
            temp = n;
            bsttodll(n.right);            
        }

Can you please calculate the time complexity here?

Do a preorder and keep adding nodes and difference = sum - node.val in hashtable. as key, value. Before adding to hash check if the difference exits in the hash table .

I do understand that this not O(1) space complexity.