Given a Binary Search Tree with only two nodes swapped. Try to find them and recover the binary search tree.

Input: 

               4

              / \

             2   6  

            / \   / \

           1  5 3  7

Output:       4

                  / \

                2   6

               /  \   / \

            1  3   5  7

 

TreeNode prev = null;
  TreeNode first = null;
  TreeNode second = null;

  public TreeNode recover(TreeNode root) {
    
    helper(root);

    int tmp = first.key;
    first.key = second.key;
    second.key = tmp;
    
    return root;
  }

  private void helper(TreeNode root) {
    if( root == null) {
      return ;
    } 
    helper(root.left);
    if(prev != null) {
      if(prev.key > root.key) {
        if(first == null) {
          first = prev;
        }
        second = root;
      }
    }
     
  
    prev = root;
    helper(root.right);

Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.

It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.

A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.

A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.

 

Example 1:


Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Example 2:

Input: preorder = [1,3]
Output: [1,null,3]

public TreeNode bstFromPreorder(int[] preorder) {
  if (preorder.length == 0) {
    return null;
  }
  return helper(preorder, 0, preorder.length - 1);
}
    
    
private TreeNode helper(int[] pre, int start, int end) {
  if (start > end) {
    return null;
  }
   
  TreeNode root = new TreeNode(pre[start]);
  if (start == end) {
    return root;
  }

  int i = start, j = end;
        
  while (i < j) {
    int mid = i + (j - i + 1) / 2;
    if (pre[mid] < pre[start]) {
      i = mid ;
    } else {
      j = mid -1;
    }
  }
   
    
    
  root.left = helper(pre, start + 1, i);
  root.right = helper(pre, i + 1, end);

  return root;
}
    
   
    

public TreeNode bstFromPreorder(int[] preorder) {
  return  bstFromPreorder(preorder, Integer.MAX_VALUE, new int[]{0});
}

public TreeNode bstFromPreorder(int[] pre, int bound, int[] i) {
  if (i[0] == pre.length || pre[i[0]] > bound) {
    return null;
  }

  TreeNode root = new TreeNode(pre[i[0]++]);
  root.left = bstFromPreorder(pre, root.val, i);
  root.right = bstFromPreorder(pre, bound, i);
  return root;
}

Given the postorder traversal sequence of a binary search tree, reconstruct the original tree.

Assumptions

The given sequence is not null
There are no duplicate keys in the binary search tree
Examples

postorder traversal = {1, 4, 3, 11, 8, 5}

the corresponding binary search tree is

        5

      /    \

    3        8

  /   \        \

1      4        11

 public TreeNode reconstruct(int[] post) {
    int len = post.length;
    if (len == 0) {
      return null;
    }
    
    return helper(post, Integer.MIN_VALUE, new int[]{len - 1});
  }

  private TreeNode helper(int[] post, int min, int[] index) {
    if (index[0] < 0 || post[index[0]] <= min) {
      return null;
    }
    TreeNode root = new TreeNode(post[index[0]--]);
 

    root.right =  helper(post, root.key, index);
       root.left =  helper(post, min, index);

  return root;
  }

Given the levelorder traversal sequence of a binary search tree, reconstruct the original tree.

Assumptions

The given sequence is not null
There are no duplicate keys in the binary search tree
Examples

levelorder traversal = {5, 3, 8, 1, 4, 11}

the corresponding binary search tree is

        5

      /    \

    3        8

  /   \        \

1      4        11

Given an array with integers, determine whether the array contains a valid postorder traversal sequence a BST.

Assumptions:

The given postorder traversal array is not null.
Examples:

For example, a1=[1, 3, 4, 2, 7, 6, 5] is a BST 

a2=[1, 3, 4, 6, 7, 2, 5] is not a BST.

public boolean validPostOrder(int[] post) {
    if (post.length == 0) {
      return true;
    }
    return helper(post, 0, post.length - 1);
  }

  private boolean helper(int[] post, int left, int right) {
    if (left >= right) {
      return true;
    }
   
    int root = post[right];
    // find left subtree's root, traverse backwards
    int leftRoot = right - 1;
    while (leftRoot >= left) {
      if (post[leftRoot] < root) {
        break;
      }
      leftRoot--;
    }
    //traver left subtree, if there is an element > root, return false
    for (int i = left; i <= leftRoot; i++) {
      if (post[i] > root) {
        return false;
      }
    }
    return helper(post, left,  leftRoot) && helper(post, leftRoot + 1, right -1);
  }

 int i = nums.length; // 7
        int max = Integer.MAX_VALUE;
        for (int j = nums.length - 1; j >= 0; j--)
        {
            if (nums[j] > max) return false; 
            while (i <= nums.length - 1 && nums[j] > nums[i])
                max = nums[i++];
            nums[--i] = nums[j];
        }
        return true;

  Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.