Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree - Problem

Imagine you have a singly linked list where all elements are arranged in perfect ascending order, like stepping stones across a river. Your mission is to transform this linear structure into a height-balanced binary search tree (BST).

A height-balanced BST is like a well-organized family tree where no branch is significantly longer than others - specifically, the depths of any two leaf nodes differ by at most 1. This ensures optimal search performance with O(log n) operations.

Input: Head of a sorted singly linked list
Output: Root of a height-balanced BST containing the same elements

The challenge lies in efficiently converting the linear structure while maintaining balance without using extra space for array conversion.

Input & Output

example_1.py — Basic Conversion

$ Input: head = [1,2,3,4,5]

› Output: TreeNode with root=3, left subtree=[1,2], right subtree=[4,5]

💡 Note: The middle element 3 becomes root. Elements [1,2] form left subtree with 2 as root and 1 as left child. Elements [4,5] form right subtree with 4 as root and 5 as right child.

example_2.py — Even Length

$ Input: head = [1,2,3,4]

› Output: TreeNode with root=2 or 3 (both valid)

💡 Note: For even length lists, either middle element can be chosen as root. Most implementations choose the left middle (2), creating balanced BST with equal subtree sizes.

example_3.py — Edge Cases

$ Input: head = [] or head = [1]

› Output: null or TreeNode(1)

💡 Note: Empty list returns null. Single node becomes a tree with just root node and no children.

Constraints

The number of nodes in head is in the range [0, 2 * 10⁴]
-10⁵ ≤ Node.val ≤ 10⁵
The linked list is guaranteed to be sorted in ascending order
Height-balanced means the depth of two leaf nodes should not differ by more than 1

Asked in

The optimal approach uses inorder simulation to build the BST in O(n) time with O(log n) space. Instead of repeatedly finding the middle element, we simulate the inorder traversal of the final BST and process each linked list node exactly once. The key insight is that inorder traversal of a BST visits nodes in the same order as the sorted linked list, allowing us to build the tree efficiently while maintaining perfect balance.

Common Approaches

Approach	Time	Space	Notes
✓ Convert to Array First (Brute Force)	O(n)	O(n)	Convert linked list to array, then build BST using array approach
Fast-Slow Pointer (Two Pointers)	O(n log n)	O(log n)	Use fast-slow pointers to find middle, then recursively build balanced BST
Inorder Simulation (Optimal)	O(n)	O(log n)	Simulate inorder traversal while building BST - optimal O(n) time, O(log n) space

Convert to Array First (Brute Force) — Algorithm Steps

Traverse the entire linked list and store values in an array
Use recursive divide-and-conquer on the array
For each subarray, pick the middle element as root
Recursively build left and right subtrees

Visualization

Tap to expand

Step-by-Step Walkthrough

Convert to Array

Traverse linked list and store values in array: [1,2,3,4,5]

Find Middle

Middle element (3) becomes root of the tree

Recursive Division

Recursively build left subtree with [1,2] and right with [4,5]

Complete Tree

Result is a balanced BST with optimal height

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

// Definition for singly-linked list
struct ListNode {
    int val;
    struct ListNode *next;
};

// Definition for binary tree node
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* arrayToBST(int* arr, int left, int right) {
    if (left > right) return NULL;
    
    int mid = left + (right - left) / 2;
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = arr[mid];
    root->left = arrayToBST(arr, left, mid - 1);
    root->right = arrayToBST(arr, mid + 1, right);
    return root;
}

struct TreeNode* sortedListToBST(struct ListNode* head) {
    // Count nodes first
    int count = 0;
    struct ListNode* curr = head;
    while (curr) {
        count++;
        curr = curr->next;
    }
    
    // Convert to array
    int* arr = (int*)malloc(count * sizeof(int));
    curr = head;
    for (int i = 0; i < count; i++) {
        arr[i] = curr->val;
        curr = curr->next;
    }
    
    struct TreeNode* result = arrayToBST(arr, 0, count - 1);
    free(arr);
    return result;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

O(n) to convert list to array + O(n) to build BST = O(n) total

✓ Linear Growth

Space Complexity

O(n)

O(n) for array storage + O(log n) recursion stack = O(n) total

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen