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.

Leetcode Problem #109 (Medium): Convert Sorted List to Binary Search Tree

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:
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 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:

(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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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);
    }
};