Java Code - O(n) time / O(lg(n)) space using DFS + Stack


  • 2
    O

    If we convert BST to sorted array and use two pointers, we need O(n) space. In fact, we only need O(lg(n)) space, by implement two iterators using stack.

    The idea of using interator is from 173. Binary Search Tree Iterator. Since the in-order treversal of BST ouputs the value in ascending order, we can use iterator to get next smallest value in O(1) average time. Similarly, we can also implement a reverse iterator to get next largest value each time from BST. (For how to use stack to implement iterator, please refer to: https://discuss.leetcode.com/topic/6604/ideal-solution-using-stack-java)

    With those two iterators in hand, now we can use two pointers to solve the problem.

    Since the size iterator(stack) is the height of the BST tree, it only requries O(lg(n)) space.

    So the overall performace is: O(n)/O(lg(n)).

    Here is my Java implementation:

        public boolean findTarget(TreeNode root, int k) {
            Stack<TreeNode> stackL = new Stack<TreeNode>();  // iterator 1 that gets next smallest value
            Stack<TreeNode> stackR = new Stack<TreeNode>();  // iterator 2 that gets next largest value
            
            for(TreeNode cur = root; cur != null; cur = cur.left)  
                stackL.push(cur);
            for(TreeNode cur = root; cur != null; cur = cur.right)  
                stackR.push(cur);
                
            while(stackL.size() != 0 && stackR.size() != 0 && stackL.peek() != stackR.peek()){
                int tmpSum = stackL.peek().val + stackR.peek().val;
                if(tmpSum == k)  return true;
                else if(tmpSum < k)
                    for(TreeNode cur = stackL.pop().right; cur != null; cur = cur.left) 
                        stackL.push(cur);
                else
                    for(TreeNode cur = stackR.pop().left; cur != null; cur = cur.right) 
                        stackR.push(cur);
            }
            
            return false;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.