# Convert Sorted List to Binary Search Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree)
Canonical: https://scaleengineer.com/dsa/problems/convert-sorted-list-to-binary-search-tree
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Linked List, Tree, Binary Tree, Binary Search Tree
**Companies:** [Meta](https://scaleengineer.com/companies/meta), [Uber](https://scaleengineer.com/companies/uber), [Lyft](https://scaleengineer.com/companies/lyft), [Zenefits](https://scaleengineer.com/companies/zenefits)
---
## 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_.

**Example 1:**

![](https://assets.glich.co/dsa/convert-sorted-list-to-binary-search-tree/image0.jpg) 

**Input:** head = [-10,-3,0,5,9]
**Output:** [0,-3,9,-10,null,5]
**Explanation:** One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

**Example 2:**

**Input:** head = []
**Output:** []

**Constraints:**

* The number of nodes in `head` is in the range `[0, 2 * 104]`.
* `-105 <= Node.val <= 105`

# Approaches
## Recursive Division using Slow and Fast Pointers
This approach builds the BST directly from the linked list without converting it to another data structure. It recursively finds the middle node of the list to serve as the root and then splits the list into two halves to form the left and right subtrees.
**Time:** O(N log N) · **Space:** O(log N)
**Pros:** Space-efficient, using only O(log N) space for the recursion stack.; Operates on the linked list in-place without needing an auxiliary data structure to store all elements.
**Cons:** The time complexity of O(N log N) is suboptimal, as the list is repeatedly traversed to find the middle element for each subtree construction.
### Explanation
The core of this method is a recursive function that takes the head and tail of a linked list segment and returns the root of the constructed BST. The segment is represented as `[head, tail)`. 

To find the middle element, which will become the root of the tree, we use the classic two-pointer technique: a `slow` pointer that moves one step at a time and a `fast` pointer that moves two steps. When the `fast` pointer reaches the `tail`, the `slow` pointer will be at the middle of the segment.

The node pointed to by `slow` becomes the root of the current subtree.
- The left subtree is recursively built from the list segment starting at the original `head` up to `slow`.
- The right subtree is recursively built from the list segment starting at `slow.next` up to `tail`.
- The base case for the recursion is when `head` and `tail` are the same, indicating an empty list segment.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        return toBST(head, null);
    }

    private TreeNode toBST(ListNode head, ListNode tail) {
        if (head == tail) {
            return null;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        // Find the middle node of the list segment [head, tail)
        while (fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 'slow' is the middle node
        TreeNode root = new TreeNode(slow.val);
        root.left = toBST(head, slow);
        root.right = toBST(slow.next, tail);
        
        return root;
    }
}
```
### Algorithm
- Handle base cases: if the list segment is empty (`head == tail`), return `null`.
- Use two pointers, `slow` and `fast`, to find the middle of the linked list segment `[head, tail)`. `slow` moves one step, `fast` moves two. Initialize both to `head`.
- Iterate while `fast != tail` and `fast.next != tail`.
- Once the middle node (`slow`) is found, create a `TreeNode` with its value. This will be the root.
- Recursively call the function for the left part, which is the segment `[head, slow)`. The result is the left child of the root.
- Recursively call the function for the right part, which is the segment `[slow.next, tail)`. The result is the right child of the root.
- Return the root.

## Convert to Array and Build Tree
This approach first converts the sorted linked list into an array. Then, it constructs a height-balanced BST from this sorted array. This simplifies the problem to "Convert Sorted Array to Binary Search Tree", as random access is much easier with an array.
**Time:** O(N) · **Space:** O(N)
**Pros:** Simple to understand and implement.; Leverages the efficiency of random access in arrays, which simplifies the logic for finding the middle element.; Time complexity is linear, which is efficient.
**Cons:** Requires extra space proportional to the number of nodes in the list (O(N)) to store the array. This can be significant for very large lists and may lead to memory issues.
### Explanation
The algorithm begins by iterating through the entire linked list and storing each node's value in a dynamic array, like an `ArrayList` in Java. This step takes O(N) time.

Once the array is populated, we have all the elements in sorted order. A recursive function is then used to build the BST. This function takes the start and end indices of the current segment of the array.

The middle element of the current array segment is chosen as the root of the subtree. This choice ensures the resulting tree is height-balanced.
- The left child of the root is constructed by recursively calling the function on the left half of the array (elements before the middle element).
- Similarly, the right child is constructed from the right half of the array.
- The base case for the recursion is when the start index becomes greater than the end index, at which point `null` is returned.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        
        // 1. Convert linked list to array
        List<Integer> values = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            values.add(current.val);
            current = current.next;
        }
        
        // 2. Build BST from the sorted array
        return buildTree(values, 0, values.size() - 1);
    }
    
    private TreeNode buildTree(List<Integer> values, int left, int right) {
        if (left > right) {
            return null;
        }
        
        // Find the middle element to be the root
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(values.get(mid));
        
        // Recursively build the left and right subtrees
        root.left = buildTree(values, left, mid - 1);
        root.right = buildTree(values, mid + 1, right);
        
        return root;
    }
}
```
### Algorithm
- Traverse the linked list and store all node values into an `ArrayList`.
- Define a recursive helper function `buildTree(values, left, right)` that constructs a BST from the subarray `values[left...right]`.
- In `buildTree`:
  - If `left > right`, return `null`.
  - Calculate the middle index `mid = left + (right - left) / 2`.
  - Create a new `TreeNode` with `values.get(mid)` as the root.
  - Set `root.left` to the result of `buildTree(values, left, mid - 1)`.
  - Set `root.right` to the result of `buildTree(values, mid + 1, right)`.
  - Return the `root`.
- Initiate the process by calling `buildTree` with the full range of the array, `(0, size - 1)`.

## Inorder Simulation with Coordinated Traversal
This is the most optimal approach. It leverages the fact that the sorted linked list represents the inorder traversal of the target BST. The tree is constructed bottom-up by simulating an inorder traversal. We don't need to find the middle node repeatedly.
**Time:** O(N) · **Space:** O(log N)
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(log N) for the recursion stack.; Traverses the linked list only once, making it very efficient.
**Cons:** The logic can be slightly less intuitive than the array-based approach.; Requires a class member or a mutable object to keep track of the list's head across recursive calls, which can be seen as a minor design drawback.
### Explanation
The algorithm first determines the size of the linked list, say `n`. A single pointer to the head of the list is maintained (e.g., as a class field). This pointer will be advanced as we 'use up' nodes from the list to build the tree.

A recursive helper function is defined, which takes a range of indices `(start, end)` representing the portion of the list to be converted into a subtree.

The logic inside the recursive function mimics an inorder traversal:
1.  **Left:** Recursively call the function for the left half of the indices, `(start, mid - 1)`. This will construct the left subtree and consume the first `mid - start` nodes from the list.
2.  **Root:** After the left subtree is built, the list pointer will be at the correct node for the current root. Create a `TreeNode` with this node's value and attach the constructed left subtree to it. Then, advance the list pointer.
3.  **Right:** Recursively call the function for the right half of the indices, `(mid + 1, end)`. This will construct the right subtree using the subsequent nodes. Attach the result as the right child of the root.

This way, we traverse the linked list only once and build the tree simultaneously.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private ListNode head;

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        this.head = head;
        int size = getListSize(head);
        return buildTree(0, size - 1);
    }

    private int getListSize(ListNode head) {
        int size = 0;
        ListNode current = head;
        while (current != null) {
            size++;
            current = current.next;
        }
        return size;
    }

    private TreeNode buildTree(int start, int end) {
        if (start > end) {
            return null;
        }

        int mid = start + (end - start) / 2;

        // 1. Recursively build the left subtree
        TreeNode leftChild = buildTree(start, mid - 1);

        // 2. Create the root node
        // After the left subtree is built, `this.head` points to the root element
        TreeNode root = new TreeNode(this.head.val);
        root.left = leftChild;

        // 3. Move head pointer to the next element for the right subtree
        this.head = this.head.next;

        // 4. Recursively build the right subtree
        root.right = buildTree(mid + 1, end);

        return root;
    }
}
```
### Algorithm
- Count the number of nodes `n` in the linked list.
- Maintain a pointer to the current `head` of the list (e.g., as a class member).
- Define a recursive helper function `buildTree(start, end)` that builds a BST from the elements corresponding to indices `start` to `end`.
- In `buildTree`:
  - If `start > end`, return `null`.
  - Calculate `mid = start + (end - start) / 2`.
  - Recursively call `buildTree(start, mid - 1)` to build the left subtree.
  - Create the root node using the value from the current `head`. Assign the returned left subtree to `root.left`.
  - Advance the `head` pointer to the next node in the list.
  - Recursively call `buildTree(mid + 1, end)` to build the right subtree. Assign the result to `root.right`.
  - Return the `root`.
- Start the process by calling `buildTree(0, n - 1)`.

# Solutions
### Java

```java
public class Convert_Sorted_List_to_Binary_Search_Tree { /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; next = null; } * } */ /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode sortedListToBST ( ListNode head ) { if ( head == null ) { return null ; } if ( head . next == null ) { return new TreeNode ( head . val ); } // find mid ListNode dummy = new ListNode ( 0 ); dummy . next = head ; ListNode slow = head , fast = head , prev = dummy ; while ( fast != null && fast . next != null ) { prev = slow ; slow = slow . next ; fast = fast . next . next ; } // prev is one before mid // ListNode 2ndPartHead = slow.next; // @note@note: illegal, cannot start with number ListNode newHead = slow . next ; prev . next = null ; // @note: cut TreeNode root = new TreeNode ( slow . val ); root . left = sortedListToBST ( head ); root . right = sortedListToBST ( newHead ); return root ; } } } ############ /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode sortedListToBST ( ListNode head ) { List < Integer > nums = new ArrayList <>(); for (; head != null ; head = head . next ) { nums . add ( head . val ); } return buildBST ( nums , 0 , nums . size () - 1 ); } private TreeNode buildBST ( List < Integer > nums , int start , int end ) { if ( start > end ) { return null ; } int mid = ( start + end ) >> 1 ; TreeNode root = new TreeNode ( nums . get ( mid )); root . left = buildBST ( nums , start , mid - 1 ); root . right = buildBST ( nums , mid + 1 , end ); return root ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {ListNode} head * @return {TreeNode} */ var sortedListToBST =
  function (head) {
    const buildBST = (nums, start, end) => {
      if (start > end) {
        return null;
      }
      const mid = (start + end) >> 1;
      const root = new TreeNode(nums[mid]);
      root.left = buildBST(nums, start, mid - 1);
      root.right = buildBST(nums, mid + 1, end);
      return root;
    };
    const nums = new Array();
    for (; head != null; head = head.next) {
      nums.push(head.val);
    }
    return buildBST(nums, 0, nums.length - 1);
  };

```

### Python

```python
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution : def sortedListToBST ( self , head : Optional [ ListNode ]) -> Optional [ TreeNode ]: if not head : return None if not head . next : return TreeNode ( head . val ) # find mid dummy = ListNode ( 0 ) dummy . next = head slow , fast , prev = head , head , dummy while fast and fast . next : prev = slow slow = slow . next fast = fast . next . next # prev is one before mid new_head = slow . next prev . next = None # cut root = TreeNode ( slow . val ) root . left = self . sortedListToBST ( head ) root . right = self . sortedListToBST ( new_head ) return root ################# class Solution : # convert to array[], extra space => but resue method in 108 def sortedListToBST ( self , head : ListNode ) -> TreeNode : def buildBST ( nums , start , end ): if start > end : return None mid = ( start + end ) >> 1 return TreeNode ( nums [ mid ], buildBST ( nums , start , mid - 1 ), buildBST ( nums , mid + 1 , end ) ) nums = [] while head : nums . append ( head . val ) head = head . next return buildBST ( nums , 0 , len ( nums ) - 1 )
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/ // Time: O(NlogN) // Space: O(logN) class Solution { int getLength ( ListNode * head ) { int ans = 0 ; for (; head ; head = head -> next , ++ ans ); return ans ; } TreeNode * dfs ( ListNode * head , int len ) { if ( len == 0 ) return NULL ; if ( len == 1 ) return new TreeNode ( head -> val ); auto p = head ; for ( int i = 0 ; i < len / 2 ; ++ i ) p = p -> next ; auto root = new TreeNode ( p -> val ); root -> left = dfs ( head , len / 2 ); root -> right = dfs ( p -> next , ( len - 1 ) / 2 ); return root ; } public: TreeNode * sortedListToBST ( ListNode * head ) { int len = getLength ( head ); return dfs ( head , len ); } };
```