Practice/Meta/Leetcode 109. Convert Sorted List to Binary Search Tree

Leetcode 109. Convert Sorted List to Binary Search Tree

CodingOptional

Problem

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

A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Requirements

1. The input linked list contains integers sorted in ascending order
2. The resulting BST must be height-balanced (left and right subtree heights differ by at most 1)
3. The resulting tree must maintain BST properties (left children < parent < right children)
4. Return the root of the constructed BST

Constraints

• The number of nodes in the linked list is in the range [0, 20000]
• -100000 ≤ Node.val ≤ 100000
• The linked list is guaranteed to be sorted in ascending order
• Time complexity: Aim for O(n) or O(n log n)
• Space complexity: O(log n) for recursion stack (not counting output tree)

Examples

Example 1:

Input: head = -10 -> -3 -> 0 -> 5 -> 9 Output: TreeNode with structure: 0 / \ -3 9 / / -10 5 Explanation: One possible balanced BST. The middle element becomes the root, and the process recursively applies to left and right halves.

Example 2:

Input: head = null Output: null Explanation: An empty list produces an empty tree.

Example 3:

Input: head = 1 Output: TreeNode(1) Explanation: A single node list produces a tree with just the root.

Example 4:

Input: head = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 Output: TreeNode with structure: 4 / \ 2 6 / \ / \ 1 3 5 7 Explanation: A perfectly balanced BST where each subtree has equal or near-equal number of nodes.