MediumLinked ListDivide and ConquerTreeBinary Search TreeBinary Tree

Convert Sorted List to Binary Search Tree

1 approach, code in every language

You are given the head of a singly linked list whose values are sorted in ascending order. Construct and return a height-balanced binary search tree containing the same values.

As with the array version, a height-balanced tree keeps the left and right subtree heights within one of each other at every node. Any valid height-balanced BST is accepted.

Example 1

Input: head = [-10,-3,0,5,9]

Output: [0,-3,9,-10,null,5]

The middle value 0 anchors the root; the elements before it form the left subtree and those after form the right subtree, producing a balanced BST.

Example 2

Input: head = []

Output: []

An empty list corresponds to an empty tree.

Constraints

The number of nodes in head is in the range [0, 2 * 10^4].
-10^5 <= Node.val <= 10^5

Inorder Simulation

Count the list length, then build nodes bottom-up while walking the list once in inorder order.

Loading animation…

Intuition

Unlike an array, a linked list gives no O(1) access to the middle, so repeatedly scanning for a midpoint would be wasteful. The trick is to notice that an inorder traversal of the target BST visits values in exactly the same order as the sorted list. So we first count the length to learn the shape of a balanced tree, then perform a simulated inorder build: recurse into the left half first, then consume the current list node as the subtree root, then recurse into the right half. A single moving pointer advances through the list in lockstep with the inorder visits, so every list node is used once and in order. This turns an otherwise O(n log n) approach into a clean linear-time construction.

Algorithm walkthrough

1Walk the list once to compute its length n; this defines the index range [0, n - 1].
2Keep a moving pointer current, initialised to head, that always points at the next value to place.
3Define build(left, right); if left > right, return null for an empty range.
4Recurse into the left half [left, mid - 1] first so earlier list values are consumed before the root.
5Create the current node from current.val, advance current to its next, then recurse into the right half [mid + 1, right].
6Return the node; build(0, n - 1) yields the balanced BST root.

Implementation

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        size = 0
        node = head
        while node:
            size += 1
            node = node.next

        self.current = head

        def build(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None
            mid = left + (right - left) // 2
            left_child = build(left, mid - 1)
            root = TreeNode(self.current.val)
            root.left = left_child
            self.current = self.current.next
            root.right = build(mid + 1, right)
            return root

        return build(0, size - 1)

Time

O(n)

Space

O(log n)

One pass counts the length and the inorder build consumes each list node once, so time is linear. The recursion depth for the balanced tree is O(log n).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Balanced Index Tree From A Reading Chain is our own problem on the technique behind Convert Sorted List to Binary Search Tree: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free