94.Binary Tree Inorder Traversal

94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Ideas:
1 use stack to store the back pointer.
2 when the node n is not null, add this node into stack, look for its left node first. so push the left node.
   when the node is null, pop the node from stack, visit this node first, then look for its right node.
    if the node is null and stack is empty, break the iteration.

    public List<Integer> inorderTraversal(TreeNode root) {

        Stack<TreeNode> stack = new Stack<TreeNode>();

        TreeNode head = root;

        List<Integer> res = new ArrayList<Integer>();

        while(true){

            if(head!=null){

                stack.add(head);

                head = head.left;

            }else{

                if(stack.isEmpty()) break;

                head = stack.pop();

                res.add(head.val);

                head = head.right;

            }

        }

        return res;

    }

173. Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Example:

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

Note:

• next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
• You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

Ideas:
approach 1: convert the tree into inorder order array.  o(1) time and o(n) space.
approach 2: o(1) time and o(logn) space.
1. initial iterator.
    new stack and put the smallest node into the stack(look for the leftmost node of the tree)
2. hasNext
    determine whether the stack is empty.
3. next
    next smallest node is from stack peek. so pop the stack n. the next smallest node after node n is the leftmost node of right subtree of the node n.
When you are on node N and are asked for next element, you obviously won’t go to the left subtree as all the elements there are smaller than N. We would go to the smallest number in the right subtree if the right subtree is not null. If the right subtree is null, that means that we need to move up, and keep moving up till we are coming from the right subtree.
                    
relative link
http://qa.geeksforgeeks.org/3996/qa.geeksforgeeks.org/3996/implement-an-iterator-over-a-binary-search-tree-bst.html

 class BSTIterator {

     Stack<TreeNode> stack;
     public BSTIterator(TreeNode root) {
         stack = new Stack<TreeNode>();
         this.pullAll(root);
     }
     
     /** @return the next smallest number */
     public int next() {
         TreeNode node = stack.pop();
         this.pullAll(node.right);
         return node.val;
     }
     
     /** @return whether we have a next smallest number */
     public boolean hasNext() {
         return !stack.isEmpty();
     }
     
     public void pullAll(TreeNode root){
         while(root != null){
             stack.add(root);
             root = root.left;
         }
     }
 }

653. Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

Example 2:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False

solution 1: o(n) time o(n) space

class Solution {
 
    public boolean findTarget(TreeNode root, int k) {
     HashSet<Integer> set = new HashSet<Integer>();
     return findUtil(root, k, set);
    }
    
    public boolean findUtil(TreeNode node, int k, HashSet<Integer> hs) {
     if(node == null) return false;
     if(hs.contains(k-node.val)) {
      return true;
     }else {
      hs.add(node.val);
     }
     return findUtil(node.left, k , hs) || findUtil(node.right, k, hs);
     
    }
}

solution 2: o(n) time o(logn) space
Ideas:
we traverse the smallest node from left, and the largest node from right. we traverse the BST in normal inorder and reverse inorder simultaneousely. In reverse inorder, we start from the rightmost node which is the maximum value node. In normal inorder, we start from the left most node which is minimum value node.
1. use boolean done1, done2 to determine which side to pick up the element

class Solution {
 
    public boolean findTarget(TreeNode root, int k) {
        Stack<TreeNode> stack1 = new Stack<TreeNode>();
        Stack<TreeNode> stack2 = new Stack<TreeNode>();
        boolean done1 = false;
        boolean done2 = false;
        TreeNode node1 = root;
        TreeNode node2 = root;
        int val1 = 0, val2 = 0;
        while(true){
            while(!done1){
                if(node1!=null){
                    stack1.push(node1);
                    node1 = node1.left;
                }else{
                    if(stack1.isEmpty()){ break;}
                    node1 = stack1.pop();
                    val1 = node1.val;
                    done1 = true;
                    node1 = node1.right;
                }
            }
            while(!done2){
                if(node2 != null){
                    stack2.push(node2);
                    node2 = node2.right;
                }else{
                    if(stack2.isEmpty()){
                        break;
                    }
                    node2 = stack2.pop();
                    val2 = node2.val;
                    done2 = true;
                    node2 = node2.left;
                }
            }
            
            if((val2 != val1) && ((val2 + val1) == k)){
                return true;
            }else if(val2 + val1 < k){
                done1 = false;
            }else if(val1 + val2 > k){
                done2 = false;
            }
            if(val1 >= val2){
                return false;
            }
        }
    }
    
}