build balanced binary search tree from sorted array

Given a sorted array, build balanced search tree based on it. The easiest way to do it is use recursion. Here I present the recursive and iterative solutions as well.


Solution 1: do it iteratively. --- working in progress, the below implementation is not correct!!!

public static Node sorted2bstIteratively(int[] nums){

assert(nums != null);

int start = 0, end = nums.length-1, mid = (start + end)>>>1;

Node root,  pre;

root = pre = new Node(nums[mid]);

end = mid -1;

while(start<=end){

mid = (start + end)>>>1;

Node n = new Node(nums[mid]);

pre.left = n;

pre = n;

end = mid - 1;

}

pre = root;

start = (nums.length-1)>>>1+1; end = nums.length-1;

while(start<=end){

mid = (start + end)>>>1;

Node n = new Node(nums[mid]);

if(pre!=null)

pre.right = n;
    pre = n;

start = mid + 1;

}

return root;

}

Solution 2: do it recursively.

public static Node sorted2bst(int[] nums){

assert(nums != null);

return sorted2bstRec(nums, 0, nums.length-1);

}

public static Node sorted2bstRec(int[] nums, int start, int end){

if(start>end)

return null;

int mid = (start+end)>>>1;

Node curr = new Node(nums[mid]);

curr.left = sorted2bstRec(nums, start, mid-1);

curr.right = sorted2bstRec(nums, mid+1, end);

return curr;

}

Order statistics binary search tree

In the past few days, Peng Li (http://allenlipeng47.com/PersonalPage/index/view/117/nkey) and I have embargoed a journey in the Trees (aka forest). Tree is a wonderful data structure, probably the most important data structure along with HashTable. In the last few blogs I talked about "Segment Tree" and its implementation. I also talked about "Skip List", which is the alternative to binary tree.

Now here is one more! Order statistics binary search tree. This is probably one of the simplest high order binary search tree. It is just like binary search tree, except we store additional information in the node, usually this additional information can be computed recursively and bubble-up approach by taking advantaging of the tree's inherent characteristics. 

For example, we can store the size of subtree rooted at each node. 

Node.size = Node.left.size + Node.right.size

Once we have that data, then we can support the following two operations in O(lgN) time.

Select(i) — find the i'th smallest element stored in the tree

Rank(x) – find the rank of element x in the tree, i.e. its index in the sorted list of elements of the tree

public class OrderStatisticTreeQ {

public class Node {

int data;

int size;

Node left;

Node right;

}

/*Select(i) — find the i'th smallest element stored in the tree

Rank(x) – find the rank of element x in the tree, i.e. its index in the sorted list of elements of the tree

*/

//k starts at 0

public int findKthSmallest(Node root, int k){

int level = k;

Node curr = root;

while(curr!=null){

int leftSize = (curr.left ==null? 0 : curr.left.size);
  if(level == leftSize )
return curr.data;
  if(leftSize > level)
curr = curr.left;
  else{
curr = curr.right;
level = level - (leftSize+1);
  }

}

return -1;

}

//index starts at 0

public int findIndexFor(Node root, int value){

Node curr = root;

int passed = 0;

while(curr!=null){

if(curr.data == value){

return (curr.left==null?0:curr.left.size) + passed;

}else if(curr.data > value){

curr = curr.left;

}else{

passed += (curr.left==null?0:curr.left.size) + 1;

curr = curr.right;

}

}

return -1;

}

}

Output of binary tree in zig-zag manner

The problem can be asked in different ways:

1. Given a binary tree and each node has an extra next pointer apart from left and right. Connect all the nodes using next pointer in Zig-Zag Manner.

2. Given a binary tree and each node has an extra next pointer apart from left and right. Print out all node in Zig-Zag Manner.

They are all coming down to how to traverse the binary tree in zig-zag manner. The key is to use two stacks, main stack and temporary stack. The main stack is used to traverse each layer, while put the children under the layer into temporary stack, also be careful with if we need to go left to right or right to left. 

public static void zigZag(Node root){

Stack<Node> s = new Stack<Node>();

s.add(root);

int level = 0;

Node pre = null;

while(!s.isEmpty()){

Stack<Node> t = new Stack<Node>();

while(!s.isEmpty()){

Node curr = s.pop();

if(pre==null)

pre = curr;

else{

pre.next = curr;

pre = curr;

}

if(level%2==0){

if(curr.left!=null)

t.add(curr.left);

if(curr.right!=null)

t.add(curr.right);

}else{

if(curr.right!=null)

t.add(curr.right);

if(curr.left!=null)

t.add(curr.left);

}

}

s = t;

level++;

}

}

Convert Binary Search Tree to Sorted Doubly-linked list

This is very interesting problem. And most of solutions are recursive approach which will cause stack overflow.

The below is my solution, which does in-place and iteratively.

The idea is to in-order traverse the tree and use head pointer referencing the head of the linked list and pre pointers referencing the previous node during traverse.

public static Node isBSTAndTreeToDLL(Node root){

if(root==null)

return null;

Stack<Node> s = new Stack<Node>();

Node head = null;

Node n = root;

Node pre = null;

while(!s.isEmpty() || n!=null){

if(n!=null){

s.push(n);

n = n.left;

}

else{

Node p = s.pop();

//this is the left most node

if(head == null)

head = p;

if(pre!=null){

pre.right = p;

p.left = pre;

}

pre=p;

n = p.right;

}

}

//handle the last node

pre.right = head;

head.left = pre;

return head;

}