Thursday, March 20, 2014

Sorted List to height-balanced binary search tree.

There is elegant algorithm to convert a Sorted List to height-balanced binary search tree in leetcode. It is asked in stackoverflow and various other websites.  This algorithm is elegant. Here I give a proof that it is correct.


public TreeNode sortedListToBST(int start, int end) {
  if (start > end)
   return null;
 
  // mid
  int mid = (start + end) / 2;
 
//first recursion 
 TreeNode left = sortedListToBST(start, mid - 1); 
 
//constant 1. There is one advance for each node inserted into tree. 
 TreeNode root = new TreeNode(h.val);
  h = h.next; 
//second recursion 
 TreeNode right = sortedListToBST(mid + 1, end);
 
  root.left = left;
  root.right = right;
 
  return root;
 }
 
Here we want to prove 
 sortedListToBST(start, end) will consume exactly end-start+1 nodes. 
If this is true, we can be certain that 1) sortedListToBST does not consume more nodes 
than expected.  2) the h is positioned for next sortedListToBST call.
 Give i=end-start, we need to prove f(i)=i+1
first, it is observed that 
f(0)=1
f(1)=2 
f(2)=3;
f(3)=f(0)+f(1)+1=4
f(4)=f(1)+f(1)+1=5.
So the statement is true for i when i<=4.
 
When i is even and i>=5.
mid=i/2.
First recursion is equal to f(mid-1-start)=f(i/2-1-0)=f(i/2-1);
Second recursion=f(end-(mid+1))=f(i-(i/2+1))=f(i/2-1).
So f(i)=f(i/2-1)+f(i/2-1)+1. Given that f(i/2)=i/2+1. We can conclude that 
f(i)=(i/2-1+1)+1 +(i/2-1+1)=i+1
So this statement is true when i>4 and i is even.


When i is odd, and i>=5.
f(i)=f((i-1)/2-1)+1+f(i-((i-1)/2+1))=(i-1)/2-1+1 + 1 + (i+1)/2-1+1=i+1.
So this statement is true for i is odd and i>=5.
 
 
It is proved! 

No comments:

Post a Comment