Convert Sorted List to Binary Search Tree (Leetcode 109)

Difficulty: Medium. Link: Day 6: May Leetcode Challenge

Problem Description

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.

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.

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 * 104].
  • -10^5 <= Node.val <= 10^5

Solution

In order to solve this problem, we need to understand two things completely LinkedList Basics and Tree In-order traversal (Would also add links for reference in the end). We are given a head of the linked list where the list is sorted so when we would traverse the linked list nodes till the end the order of values would be sorted. We can use this idea to have a sorted list of integers for easy access.

Now to covert a sorted list into a height balanced binary tree, We would have to recursively bisect the values with mid value being the parent node. This helps to ensure that there are roughly half nodes on both of the sides of the parent. Since we have transformed list nodes values on an array, we can easily partition the list into two halves by calculating the mid point(count/2).

Partition

We can define a helper function to recursively partition the node and we can use the binary search search like strategy on both sides to build left and right values of the tree. The for any part of the list, the root node would the middle value (mid). Then left part can be created from indexes (low…mid -1 ) and right subtree can be formed using (mid+1…end). This will recursively go on until whole list is transformed in a tree. We can simply return the tree head as result.

Optimisation : Tree In-order

The above solution is using a space of O(N). Why? Because we traversed the linked list and sorted a list of values for easier access. How would be improve that? If you understand Tree In-order traversal , we can use the order for our advantage and discard the array of values. The Tree In-order on a Binary search tree would give output in the sorted order. Hmmm…. And what linked list traversal of input gives us? Sorted order!. Interesting, what if we could sync both of the operations together then we can find the value of the node from the current list iterator. We’ll just need to make sure we move current to current.next at the end of processing the middle node. We can maintain the traversal order in the helper function by first recursively calling out for left sub tree, then the root node and finally the right subtree. This would not use any extra space but because of the recursion, the stack space of O(LogN) would be consumed which is better than O(N) right?.

But we still need to iterate the list once to count the elements.

Swift

class Solution {
func sortedListToBST(_ head: ListNode?) -> TreeNode? {
var sortedList = [Int]()
var current:ListNode? = head
while let node = current {
sortedList.append(node.val)
current = node.next
}
let rootNode = partition_helper(sortedList, 0, sortedList.count 1)
return rootNode
}
func partition_helper(_ list:[Int], _ left: Int, _ right:Int) -> TreeNode? {
guard left <= right else { return nil}
let mid = left + (right left ) / 2
let node = TreeNode(list[mid])
node.left = partition_helper(list, left, mid 1)
node.right = partition_helper(list,mid + 1, right)
return node
}
}

Swift: Optimised

class Solution {
var current:ListNode?
func sortedListToBST(_ head: ListNode?) -> TreeNode? {
var count = 0
var curr: ListNode? = head
while curr != nil {
count += 1
curr = curr?.next
}
current = head
let rootNode = partition_helper(1,count)
return rootNode
}
func partition_helper(_ left: Int, _ right:Int) -> TreeNode? {
guard left <= right else { return nil}
let mid = left + (right left ) / 2
let node = TreeNode()
// Inorder : Left -> Root -> Right
node.left = partition_helper(left, mid 1)
node.val = current!.val
// Move the list pointer
current = current?.next
node.right = partition_helper(mid + 1, right)
return node
}
}

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

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

Complexity Analysis

Complexity analysis is already discussion in the optimisation section.

  • Time = O(N) where N is the length of the linked list
  • Space = O(log N)  due to the recursion stack

Links

Tree basic

Linked List traversal

Inorder traversal

Sorted list to Binary Tree

Leave a Reply

Your email address will not be published. Required fields are marked *