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