Difficulty: Medium. Link: Day 6: May Leetcode Challenge
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.
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.
Input: head =  Output: 
Input: head =  Output: 
Input: head = [1,3] Output: [3,1]
- The number of nodes in
headis in the range
[0, 2 * 104].
-10^5 <= Node.val <= 10^5
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).
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.
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