Solution: Convert Sorted List to Binary Search Tree
Tags: algorithms, javascript, java, python
Published: 2021-05-06 10:36:49

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/1194228).*

---

#### [Leetcode Problem #109 (*Medium*): Convert Sorted List to Binary Search Tree](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Given the `head` of a singly linked list where elements are **sorted in ascending order**, convert it to a height balanced BST.
>
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
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.
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2020/08/17/linked.jpg)
>
Example 2:||
|---:|---|
Input:|head = []
Output:|[]
>
Example 3:||
|---:|---|
Input:|head = [0]
Output:|[0]
>
Example 4:||
|---:|---|
Input:|head = [1,3]
Output:|[3,1]

---

#### ***Constraints:***
>
 - The number of nodes in head is in the range `[0, 2 * 10^4]`.
 - `-10^5 <= Node.val <= 10^5`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

In order to build a **height-balanced binary tree**, we need to ensure that roughly half of the total number of nodes are on either side of the root, and the only way to know what half of the total number of nodes is requires finding the total number of nodes first.

With this in mind, one easy solution would be to convert the linked list to an array, then we have handy access not only to the total length of the array, but also index-access to the node values, as well. At that point, we could define a **recursive** helper to build a tree from the middle node, recursively calling itself to build subtrees from the nodes on the left and right of the middle node. This option would take an **extra O(N) space** to complete.

Should we not want to use up that much extra space, we could instead keep the linked list and lose the index-access nature of the array, using **Floyd's Cycle Detection Algorithm** to easily find the middle node on each recursion step. This would, however, require iterating through parts of the linked list repeatedly, driving the **time complexity** from **O(N)** to **O(N log N)**.

But we can do even better: We can complete this problem in **O(N) time** with only **O(log N) extra space** (in excess of the output space).

First, we'll have to iterate once through the linked list to count the total number of nodes (**count**). Then, we can define our recursive helper (**treeify()**)using index numbers as our arguments. Even though we won't be able to access the listnodes directly by index number, we can take advantage of an **inorder tree traversal** to force our access to go in iterative order.

We'll need to have our list pointer (**curr**) have global scope in order to update properly via recursion. In an inorder traversal, we recursively process the left subtree, then process the middle node, then recursively process the right subtree. For this solution, we'll just need to make sure we move **curr** to **curr.next** at the end of processing the middle node.

We can then **return** the full tree built by our recursive helper.

 - _**Time Complexity: O(N)** where **N** is the length of the linked list_
 - _**Space Complexity: O(log N)** in excess of the space needed for the input/output, due to the recursion stack_

---

#### ***Implementation:***

For Python, we can store our list index pointer (**curr**) in a list to give it global scope so that it will update properly.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var sortedListToBST = function(head) {
    let curr = head, count = 0
    while (curr) curr = curr.next, count++
    const treeify = (i, j) => {
        if (j < i) return null
        let mid = i + j >> 1, node = new TreeNode()
        node.left = treeify(i, mid - 1)
        node.val = curr.val, curr = curr.next
        node.right = treeify(mid + 1, j)
        return node
    }
    curr = head
    return treeify(1, count)
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        curr, count = head, 0
        while curr:
            curr = curr.next
            count += 1
        def treeify(i: int, j: int) -> TreeNode:
            if j < i: return None
            mid, node = i + j >> 1, TreeNode()
            node.left = treeify(i, mid - 1)
            node.val, curr[0] = curr[0].val, curr[0].next
            node.right = treeify(mid + 1, j)
            return node
        curr = [head]
        return treeify(1, count)
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    ListNode curr;
    public TreeNode sortedListToBST(ListNode head) {
        int count = 0;
        curr = head;
        while (curr != null) {
            curr = curr.next;
            count++;
        }
        curr = head;
        return treeify(1, count);
    }
    private TreeNode treeify(int i, int j) {
        if (j < i) return null;
        int mid = i + j >> 1;
        TreeNode node = new TreeNode();
        node.left = treeify(i, mid - 1);
        node.val = curr.val;
        curr = curr.next;
        node.right = treeify(mid + 1, j);
        return node;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
private:
    ListNode* curr;
    TreeNode* treeify(int i, int j) {
        if (j < i) return nullptr;
        int mid = (i + j) >> 1;
        TreeNode* node = new TreeNode();
        node->left = treeify(i, mid - 1);
        node->val = curr->val, curr = curr->next;
        node->right = treeify(mid + 1, j);
        return node;
    }
public:
    TreeNode* sortedListToBST(ListNode* head) {
        int count = 0;
        curr = head;
        while (curr) curr = curr->next, count++;
        curr = head;
        return treeify(1, count);
    }
};
```