## DEV Community is a community of 867,901 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

seanpgallivan

Posted on

# Solution: Convert Sorted List to Binary Search Tree

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

#### Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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:
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 2:
Output: []
Example 3:
Output: [0]
Example 4:
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:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

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:

``````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
}
return treeify(1, count)
};
``````

#### Python Code:

``````class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
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
return treeify(1, count)
``````

#### Java Code:

``````class Solution {
ListNode curr;
int count = 0;
while (curr != null) {
curr = curr.next;
count++;
}
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:

``````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:
int count = 0;
while (curr) curr = curr->next, count++;
return treeify(1, count);
}
};
``````

## Discussion (1)

Rohith V

Sharing my solution

``````/**
* 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 {
return null;
ListNode previousSlow = null;
while (fast != null && fast.next != null) {
previousSlow = slow;
slow = slow.next;
fast = fast.next.next;
}
previousSlow.next = null;
TreeNode root = new TreeNode(slow.val);