Frontend Prep

Appearance

Convert Sorted Linked List to Balanced BST ​

Frequently Asked at Salesforce OA — Reported repeatedly in Salesforce HackerRank OAs (2024-2026).

Problem Statement ​

Given the head of a singly linked list in ascending order, convert it to a height-balanced binary search tree. A height-balanced BST is one where the depths of the two subtrees of every node differ by at most 1.

Example 1:

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

One valid output:
        0
       / \
     -3   9
     /   /
   -10  5

Example 2:

Input: head = []
Output: null

Constraints:

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

Difficulty: Medium LC: 109 Round: OA

Pattern Recognition ​

  • What is the input structure? A sorted singly linked list.
  • What are we optimizing? Build a height-balanced BST.
  • What pattern does this fit? Divide and conquer. The middle element becomes the root; the left half becomes the left subtree; the right half becomes the right subtree.
  • Why does this pattern fit? A sorted sequence produces a balanced BST precisely when you recursively pick the middle as root. For a sorted array this is trivial indexing; for a linked list you either (a) convert to an array first, or (b) use slow/fast pointers to find midpoints.

Approach ​

Brute Force — Repeated Midpoint via Slow/Fast Pointer ​

At each recursive call, scan the sublist with slow/fast pointers to find the middle. Recurse on the left half (same head, cut before middle) and the right half (after middle).

Time: O(n log n) — each level does O(n) midpoint work across all recursive calls, and there are log n levels. Space: O(log n) recursion stack. Why this is not actually "brute" but slower than needed: the repeated linear walks add a log factor. Still correct; often acceptable.

Optimal — Convert to Array First ​

Key Insight: Once you have random access (an array), building a balanced BST is a clean recursive O(n) with mid = (lo + hi) / 2 at each step.

Step-by-step:

  1. Walk the linked list once, pushing values into an array.
  2. Recursively build: build(lo, hi) returns null if lo > hi, else creates a node from arr[mid], recursing into build(lo, mid-1) as left child and build(mid+1, hi) as right child.

Time: O(n) — each index touched once during array build and once during recursion. Space: O(n) for the array + O(log n) recursion stack.

You trade O(n) extra memory for clarity and a log-factor speedup. At OA time, this is almost always the right call.

Alternative — Inorder Simulation with a Pointer ​

Convert to an array only conceptually: walk the list with a global pointer, build the tree via inorder recursion using only the count of nodes. Slightly more elegant, same complexity.

Walkthrough ​

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

  1. Copy list into array: arr = [-10, -3, 0, 5, 9], n = 5.
  2. build(0, 4): mid = 2, root = 0.
    • Left subtree = build(0, 1).
    • Right subtree = build(3, 4).
  3. build(0, 1): mid = 0, root = -10.
    • Left = build(0, -1) → null.
    • Right = build(1, 1) → node -3 with null children.
  4. build(3, 4): mid = 3, root = 5.
    • Left = build(3, 2) → null.
    • Right = build(4, 4) → node 9 with null children.

Final tree:

        0
       / \
     -10   5
       \    \
       -3    9

This is height-balanced: left subtree depth = 2, right subtree depth = 2, difference = 0. At node -10, left depth = 0 (null), right depth = 1 (node -3), diff = 1, still balanced.

Note: with mid = (lo + hi) >> 1 you get the lower middle. LeetCode accepts either the lower or upper middle — both produce valid balanced BSTs, though the tree shape differs.

Implementation ​

typescript
class ListNode {
    val: number;
    next: ListNode | null;
    constructor(v: number = 0, n: ListNode | null = null) {
        this.val = v;
        this.next = n;
    }
}

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(v: number = 0) {
        this.val = v;
        this.left = null;
        this.right = null;
    }
}

function sortedListToBST(head: ListNode | null): TreeNode | null {
    // 1. Copy list into array for O(1) random access.
    const arr: number[] = [];
    for (let cur = head; cur; cur = cur.next) arr.push(cur.val);

    // 2. Recursively build balanced BST from [lo, hi].
    const build = (lo: number, hi: number): TreeNode | null => {
        if (lo > hi) return null;
        const mid = (lo + hi) >> 1;
        const node = new TreeNode(arr[mid]);
        node.left = build(lo, mid - 1);
        node.right = build(mid + 1, hi);
        return node;
    };
    return build(0, arr.length - 1);
}
cpp
#include <vector>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

TreeNode* build(const std::vector<int>& arr, int lo, int hi) {
    if (lo > hi) return nullptr;
    int mid = (lo + hi) / 2;
    TreeNode* node = new TreeNode(arr[mid]);
    node->left = build(arr, lo, mid - 1);
    node->right = build(arr, mid + 1, hi);
    return node;
}

TreeNode* sortedListToBST(ListNode* head) {
    std::vector<int> arr;
    for (auto cur = head; cur; cur = cur->next) arr.push_back(cur->val);
    return build(arr, 0, (int)arr.size() - 1);
}

Watch out:

  1. Off-by-one on mid. (lo + hi) >> 1 picks the lower midpoint; (lo + hi + 1) >> 1 picks the upper. Either is valid but pick one and be consistent.
  2. Using slow/fast pointers per recursion. Correct but adds a log factor. At OA time, array conversion is faster to write and analyze.
  3. Empty list. Must return null immediately. The base case lo > hi handles this naturally.

Complexity Analysis ​

TimeSpace
Slow/Fast Per CallO(n log n)O(log n)
Array Conversion (Optimal)O(n)O(n)

Bottleneck: Array conversion reads each node once and builds each tree node once. You cannot go below O(n) — every value must appear in the tree.

Edge Cases ​

  1. Empty list — return null. The array is empty, build(0, -1) returns null immediately.
  2. Single node — tree is a single node with null children.
  3. Two nodes — one becomes root, the other becomes a child. Height difference = 1, still balanced.
  4. Already balanced input length (power of 2 minus 1) — perfectly balanced result.
  5. All duplicate values — still a valid BST (duplicates allowed on one side, depending on convention).
  6. Very long list near the 20,000 node limit — the O(n) + O(n) approach is fine. An O(n log n) approach might creep toward the time limit on HackerRank.
  • LC 108 — Convert Sorted Array to Binary Search Tree — This problem minus the linked-list step. Identical recursion once you have an array.
  • LC 110 — Balanced Binary Tree — Verify a tree is height-balanced. Natural follow-up.
  • LC 95 — Unique Binary Search Trees II — Enumerate all valid BSTs on 1..n. Same divide-and-conquer skeleton.
  • LC 1382 — Balance a Binary Search Tree — Given any BST, rebalance it. Inorder to array, then this problem.

OA Strategy Notes ​

This is a solid warmup if it is your problem 1. Aim to submit within 15 minutes. The key risk is overengineering with slow/fast pointers under time pressure — the array version is simpler, more reliable, and well within the memory limit for n <= 20,000.

What is Expected at Each Level ​

Junior: Recognize divide and conquer. Likely reaches for the array approach first. May need help cutting the list in half for the slow/fast pointer variant.

Mid-level: Delivers the array approach cleanly. Explains why the midpoint produces balance. Discusses the O(n log n) vs O(n) tradeoff.

Senior: Implements the inorder-pointer variant that avoids O(n) extra space (treats the linked list cursor as a global, builds left subtree first, consumes current node as root, then builds right subtree). Analyzes trees with duplicate values and discusses balance invariants precisely.

Frontend interview preparation reference.