Skip to main content

79. Convert Sorted List to Binary Search Tree

mediumAsked at Ola

Convert a sorted linked list into a height-balanced BST.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given the head of a singly linked list where elements are sorted in ascending order, convert it into a height-balanced binary search tree.

Constraints

  • Number of nodes is in [0, 2*10^4]
  • -10^5 <= Node.val <= 10^5

Examples

Example 1

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

Example 2

Input
head = []
Output
[]

Approaches

1. Read into array first

Convert list to array then build BST by indexing at the middle of each range.

Time
O(n)
Space
O(n)
const arr = []; let n = head; while (n) { arr.push(n.val); n = n.next; }
const build = (lo, hi) => { if (lo > hi) return null; const mid = (lo+hi)>>1; return { val: arr[mid], left: build(lo, mid-1), right: build(mid+1, hi) }; };
return build(0, arr.length - 1);

Tradeoff:

2. Inorder walk with pointer

Count list length; recursively build left, take next list node as root, build right. Inorder pointer advances exactly once per call.

Time
O(n)
Space
O(log n)
function sortedListToBST(head) {
  let n = head, len = 0; while (n) { len++; n = n.next; }
  let curr = head;
  const build = (lo, hi) => {
    if (lo > hi) return null;
    const mid = (lo + hi) >> 1;
    const left = build(lo, mid - 1);
    const root = { val: curr.val, left, right: null };
    curr = curr.next;
    root.right = build(mid + 1, hi);
    return root;
  };
  return build(0, len - 1);
}

Tradeoff:

Ola-specific tips

Ola probes whether you can avoid the array copy; tie it to incrementally building a balanced lookup over a long sorted GPS-history stream.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Convert Sorted List to Binary Search Tree and other Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →