Leetcode 109: Convert sorted list to binary search tree

Feb. 18, 2018

Introduction

It is so excited to share my practice experience today. I had discussion with the peer on the algorithm Leetcode 109. The peer asked me to give him a tree problem, recursive solution problem. His request is based on the fact that recursive function is hard to figure out but it is easy to write in a few minutes.

Mock interview discussion

The peer wrote his analysis and spent around 10 minutes. I asked what is time complexity for his algorithm. He told me that it will be O(N²). So I chose one of leetcode discussion and then asked him having a discussion based on the solution provided over there.

Here is the discussion we had on the post on the leetcode discussion. O(n) time solution with O(1) space.

I will write down 5 minutes talk I gave to the peer. I just could not believe that I did make some comment and also the peer seems to like my comment.


There are two things to talk about related to the algorithm:

1. First the binary search tree inorder traversal will output the tree nodes in the ascending order;
2. If there is only one node in the sorted list, how to convert the list the binary search tree? What is the time complexity?

Definitely the node will be the root of the tree, and then left substree is empty and right subtree is empty.  Assume that the hint is given to traversal the tree once from the list.

The recursive function is designed this way that it is against the intuitive. The tip is that do not overthink, be a lazy and relaxed programmer. Work on the minimum coding and thinking. The linked list will travel once to next in the recursive function. If the linked list is one node, the travel will go to null from the start node.

The reason I made this talk is to remind myself that next time I come cross the problem, I will not be nervous, and I can figure out in less than five minutes.