Convert Sorted List to BST
Medium · Arrays & Hashing · Linked List · Divide and Conquer · Tree · Binary Search Tree · Binary Tree
Problem
You are given the head of a singly linked list whose values are sorted in ascending order. Build a height-balanced binary search tree containing exactly those values and return its root.
A binary tree is height-balanced when, at every node, the depths of the left and right subtrees differ by at most one. Several balanced trees may be valid; any of them is accepted. The examples pick the middle element (the upper one when the count is even) as each root.
Examples
Input: head = [1,2,3,4] Output: [3,2,4,1]
3 becomes the root, 2 (with child 1) goes left, and 4 goes right.
Input: head = [-5,0,7] Output: [0,-5,7]
The middle value 0 is the root with one value on each side.
Input: head = [] Output: []
An empty list gives an empty tree.
Constraints
- The number of nodes in the list is in the range [0, 10^4]
- -10^5 <= Node.val <= 10^5
- The values are sorted in non-decreasing order
Approaches
- Baseline: find each middle with slow and fast pointers — time O(n log n), space O(log n)
Follow-up
The in-order build reads the list strictly forward, so it works on any sorted stream. The use cases fix the middle-choice rule so the tree is unique, then write its preorder and the search path of a value, both straight from the sorted values.
Related problems
Start free on Cariara · Coding problems · System design studio
