Leetcode 109. Convert sorted list to binary search tree

Sept. 10, 2018

Introduction

It is my favorite tree algorithm. I had chance to work on the algorithms since I asked the algorithm in mock interview at 10:00 PM as an interviewer. I had discussion with the peer on time complexity, I asked if the solution is bottom up or top down.

In order to clear my doubt, I look up Leetcode discuss, and then I know that geeksforgeeks.com should have the correct answer. Here is the link.

My practice

I like to write C# code and practice this algorithm again.

I found this article is very well written for the optimal time complexity solution, and then I wrote a C# code based on that.

My code is here.

My favorite article 

I like to copy the analysis from the article and share here first. I like to highlight a few words for me to memorize the approach better.

Naive Solution:

A naive way is to apply the previous solution directly. In each recursive call, you would have to traverse half of the list’s length to find the middle element. The run time complexity is clearly O(N lg N), where N is the total number of elements in the list. This is because each level of recursive call requires a total of N/2 traversal steps in the list, and there are a total of lg N number of levels (ie, the height of the balanced tree).

Hint:

How about inserting nodes following the list’s order? If we can achieve this, we no longer need to find the middle element, as we are able to traverse the list while inserting nodes to the tree.

Best Solution:

As usual, the best solution requires you to think from another perspective. In other words, we no longer create nodes in the tree using the top-down approach. We create nodes bottom-up, and assign them to its parents. The bottom-up approach enables us to access the list in its order while creating nodes.

Isn’t the bottom-up approach neat? Each time you are stucked with the top-down approach, give bottom-up a try. Although bottom-up approach is not the most natural way we think, it is extremely helpful in some cases. However, you should prefer top-down instead of bottom-up in general, since the latter is more difficult to verify in correctness.

Below is the code for converting a singly linked list to a balanced BST. Please note that the algorithm requires the list’s length to be passed in as the function’s parameters. The list’s length could be found in O(N) time by traversing the entire list’s once. The recursive calls traverse the list and create tree’s nodes by the list’s order, which also takes O(N) time. Therefore, the overall run time complexity is still O(N).

My argument of bottom-up approach

The idea of linear time solution is to iterate the single linked list once, and each node visited will be the root node inside inorder traversal recursive function. 

How to reason that? 

We know that binary search tree inorder traversal is to visit left child, root node and then right child. So that the inorder traversal of binary search tree will be in ascending order. Every visited node will be the root node which is visited once and only once.