Convert Sorted Array to Binary Search Tree

Most of the time, when writing code for a Technical Interview or just to on Data Structures & Algorithms skills, sometimes is forgotten two important aspects: and being in the Programming Language being used. brush up Code Quality idiomatic That's why I decided to write this post. This post will go through some concepts. Kotlin Understanding the problem The LeetCode problem the following, states Given an integer array where the elements are sorted in ascending order, convert it to a height-balanced[^1] binary search tree. nums Before we start off, there are some important observations: is already sorted. nums An is given as an . So, accessing an element will be a constant-time operation . Array input O(1) The length is at most so the time complexity must be one. nums 10^4 a good The resulting Binary Search Tree must be . height-balanced That's the LeetCode definition of a Binary Tree: class TreeNode(var `val`: Int) { var left: TreeNode? = null var right: TreeNode? = null } Algorithm (Recursive solution) Here's when technique comes into play. Divide and Conquer These are the steps to follow to create the BST: Let the size of the array and the index of the middle element, and pick as the . n A m = n/2 A[m] root of the BST[^2] Consider the two following contiguous subarrays; and respectively with as a 0-indexed array, the left and right sub contiguous subarrays. A[… m-1] A[m+1 …] A Create the left and right subtrees with and sub contiguous subarrays recursively following step . A[… m-1] A[m+1 …] (1) Repeat recursively until an empty subarray is encountered. When this happens the node will hold a value. null The following diagram depicts the idea: Kotlin Implementation class Solution { fun sortedArrayToBST(nums: IntArray): TreeNode? { fun makeTree(start: Int, end: Int): TreeNode? = if (start >= end) { null } else { val mid = start + (end - start) / 2 TreeNode(nums[mid]).apply { left = makeTree(start, mid) right = makeTree(mid + 1, end) } } return makeTree(0, nums.size) } } Code Analysis Kotlin provides a in the type system. That's the reason the type is instead of . Null safety TreeNode? TreeNode We can know when a value is nullable or not at compile-time. A was created for building the tree. Note that is accessible inside the function. Local function makeTree nums makeTree The and are used as delimiters in the Binary Search. The reason is to avoid the creation of new subarrays. start end When performing a Binary Search within a range, there's a common mistake that leads to integer overflow[^3]. That snippet would cause an overflow val mid = (start + end) / 2 In order to avoid overflow, the index is computed as mid val mid = start + (end - start) / 2 In Kotlin, is an , it returns a value. Taking advantage of that property, either returns an empty node ( ) or a . if expression makeTree null TreeNode Returns if there isn't a valid range to look up in the Binary Search. null A new having as an element the as value and, the left and right subtrees are built recursively. TreeNode mid The function is a . Is used for assigning the values of the and subtrees. It's convenient when modifying the properties of a class in a Kotlin-idiomatic way. apply Scope function left right TreeNode(nums[mid]).apply { left = makeTree(start, mid) right = makeTree(mid + 1, end) } Complexity Analysis : , where stands for the size of the array. Time complexity O(n) n : , where stands for the height of the BST. The maximum depth of the recursion in the stack is . Space complexity O(h) h h Ergo, the BST is built in linear time and the space needed is . h [^1]: A binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one. height-balanced [^2]: For the sake of simplicity, will stand for Binary Search Tree. BST [^3]: Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken