Swift Leetcode Series : Convert Sorted List to Binary Search Tree

Swift + BST + Tree inorder + LinkedList = Leetcode 109 ✅ ✅ ✅

Convert Sorted List to Binary Search Tree (Leetcode 109) -

You can check out the full story on The Swift Nerd blog with the link above.

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

Check out the detailed explanation on the blog.

Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!

You can find me on TheSwiftNerd | LinkedIn | Github