## 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! `