Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree

What is this problem about?

The Convert Sorted List to Binary Search Tree coding problem is a more challenging version of the array-to-BST problem. Here, you are given a singly linked list where values are sorted in ascending order. You must convert it into a height-balanced BST. The difficulty arises from the fact that you cannot access the middle element of a linked list in O(1) time like you can with an array.

Why is this asked in interviews?

Uber, Meta, and Google use the Convert Sorted List to Binary Search Tree interview question to see if a candidate can optimize a recursive algorithm for a less flexible data structure. It tests your ability to handle two pointers (Slow and Fast) to find the middle, or your ability to use a more advanced "in-order simulation" to build the tree while traversing the list once.

Algorithmic pattern used

There are two common Tree interview patterns for this:

1. Fast and Slow Pointers: Use two pointers to find the middle of the current list segment. Use the middle as the root and recurse on the left and right halves. (O(N log N) time).
2. In-order Simulation (Optimal): Since an in-order traversal of a BST visits nodes in sorted order, you can build the tree structure first and fill it with values from the linked list as you traverse it. (O(N) time).

Example explanation

List: 1 -> 2 -> 3 -> 4 -> 5 Using Fast/Slow Pointers:

1. Fast moves 2 steps, Slow moves 1 step.
2. When Fast reaches the end, Slow is at 3.
3. 3 becomes the root.
4. Split the list: [1, 2] and [4, 5].
5. Recurse on [1, 2]. Slow finds 1 (or 2).
6. Build subtrees accordingly.

Common mistakes candidates make

• Infinite Recursion: Not properly disconnecting the list at the middle node when using the pointer approach.
• Efficiency: Using a naive O(N^2) approach by re-traversing the list from the head for every single recursive call.
• Space Complexity: Converting the linked list into an array first. While this works, interviewers often want to see a solution that works directly on the list or uses minimal extra space.

Interview preparation tip

The O(N) in-order simulation is highly impressive. It involves keeping a global pointer to the current list node and moving it forward every time a tree node is "created" during the recursive calls.