Problem statement

Given the head of a singly linked list whose values are in strictly increasing order, build a height-balanced binary search tree holding the same values and return its root. (Height-balanced: for every node, the depths of its two subtrees differ by at most one.)

To make the answer unique, build it this way: for the values at positions lo..hi (0-based), the root is the value at position (lo + hi) / 2 rounded down — the left-middle one — its left subtree is built from lo..mid-1 and its right subtree from mid+1..hi.

Example 1

Input: head = [-10,-3,0,5,9]
Output: [0,-10,5,null,-3,null,9]
Explanation: 0 is the middle value; -10 roots [-10,-3] and 5 roots [5,9].

Example 2

Input: head = []
Output: []

Example 3

Input: head = [1,3]
Output: [1,null,3]
Explanation: For two values the left-middle one, 1, is the root.

Constraints

• The number of nodes in the list is in the range [0, 2 * 10^4]
• -10^5 <= Node.val <= 10^5
• The values are strictly increasing

Hints for Convert Sorted List to Binary Search Tree

1. Hint 1

   In a BST built from sorted values, the root splits the values into the smaller ones (left) and larger ones (right). Taking the middle as root keeps the two sides balanced.

2. Hint 2

   With an array you could jump to the middle; a list cannot. But an in-order traversal of the finished tree visits the values in exactly the list's order.

3. Hint 3

   Count the nodes, then build recursively by index range: build the left subtree first (it consumes the list's next values), then create the root from the current list node and advance, then build the right subtree.

How to solve Convert Sorted List to Binary Search Tree

The tree's in-order sequence must equal the list. So build the tree in in-order: recursing on the index range lo..hi, first build the left subtree from lo..mid-1, which consumes exactly the list's next mid - lo values, then the list's current node is the root, then build the right subtree. A single cursor walks the list once.

Approach

1. Count the nodes n; set a cursor cur = head.
2. Define build(lo, hi): if lo > hi return null; mid = (lo + hi) / 2.
3. left = build(lo, mid - 1); create root with cur.val; advance cur; root.left = left; root.right = build(mid + 1, hi); return root.
4. Return build(0, n - 1).

Why it works

By induction, build(lo, hi) consumes exactly hi - lo + 1 list nodes in order and returns a tree whose in-order sequence is those values, rooted at position mid of the range. Since the list is sorted, every left value is smaller and every right value larger, so it is a BST; choosing the middle makes the two sides differ in size by at most one, which keeps it height-balanced, and the left-middle rule fixes the exact shape.

Complexity

• Time — O(n)
• Space — O(log n) for the recursion

Pitfalls

• Finding the middle with slow/fast pointers on every call works but costs O(n log n), and the usual slow/fast loop picks the right-middle of an even range — a different tree.
• Build the left subtree before creating the root; the cursor must have passed the left values first.
• Copying the values into an array and building from the middle index is a simpler O(n)-space alternative that gives the same tree.

Reference solution

Python

from typing import Optional

def sortedListToBST(head: Optional[ListNode]) -> Optional[TreeNode]:
    n = 0
    p = head
    while p:
        n += 1
        p = p.next
    cur = head

    def build(lo, hi):
        nonlocal cur
        if lo > hi:
            return None
        mid = (lo + hi) // 2
        left = build(lo, mid - 1)
        root = TreeNode(cur.val)
        cur = cur.next
        root.left = left
        root.right = build(mid + 1, hi)
        return root

    return build(0, n - 1)

Java

public static TreeNode sortedListToBST(ListNode head) {
    int n = 0;
    for (ListNode p = head; p != null; p = p.next) n++;
    ListNode[] cur = { head };
    return buildRange(cur, 0, n - 1);
}

static TreeNode buildRange(ListNode[] cur, int lo, int hi) {
    if (lo > hi) return null;
    int mid = (lo + hi) / 2;
    TreeNode left = buildRange(cur, lo, mid - 1);
    TreeNode root = new TreeNode(cur[0].val);
    cur[0] = cur[0].next;
    root.left = left;
    root.right = buildRange(cur, mid + 1, hi);
    return root;
}

C++

TreeNode* sortedListToBST(ListNode* head) {
    int n = 0;
    for (ListNode* p = head; p; p = p->next) n++;
    ListNode* cur = head;
    function<TreeNode*(int, int)> build = [&](int lo, int hi) -> TreeNode* {
        if (lo > hi) return nullptr;
        int mid = (lo + hi) / 2;
        TreeNode* left = build(lo, mid - 1);
        TreeNode* root = new TreeNode(cur->val);
        cur = cur->next;
        root->left = left;
        root->right = build(mid + 1, hi);
        return root;
    };
    return build(0, n - 1);
}

JavaScript

var sortedListToBST = function(head) {
    var n = 0;
    for (var p = head; p !== null; p = p.next) n++;
    var cur = head;
    var build = function(lo, hi) {
        if (lo > hi) return null;
        var mid = Math.floor((lo + hi) / 2);
        var left = build(lo, mid - 1);
        var root = new TreeNode(cur.val);
        cur = cur.next;
        root.left = left;
        root.right = build(mid + 1, hi);
        return root;
    };
    return build(0, n - 1);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More trees problems

• Operations on Tree Medium
• Throne Inheritance Medium
• Foldable Binary Tree Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium
• Duplicate Subtree in Binary Tree Medium
• Sum of Nodes on the Longest Path from Root to Leaf Medium