Convert Sorted Array To Binary Search Tree

Problem

• Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree

Example:

Input: nums = [-10,-3,0,5,9]

Output: [0,-3,9,-10,null,5]

Approach

• 1. Make the middle of the array the head node's value
• 2. Split the array into a left array and right array
• 3. Recursive call on the helper function insert on node.Left and node.Right with left array and right array respectively
• 4. Base Case: len(nums) == 1, means the array has been cut as far as it can be.
• 5. Recursive Step: Bullets 1-3

Edge Cases

• Input: [] -> null

Reflections

I am honestly quite proud of myself for thinking of this solution without any outside help. I do not believe that this is an easy problem.

After looking at other peoples solutions, I recognize that the helper insert function is not explicity necessary. However, when I used other peoples solutions where they just recursively called the primary function, their solutions ended up all being far less optimal as far as memory is concerned, as in a factor of 3 worse (25% vs 75%).

I also now know that you do not have to initialize all of the values in a struct in a Go, I just always assumed that because it is a strongly typed language that you have to intialize left and right as nil on a tree node for example but you dont.

Go Solution

func sortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 1 {
		return createNode(nums[0])
	}

	mid := len(nums) / 2

	leftArr := nums[:mid]
	rightArr := nums[mid+1:]

	head := createNode(nums[mid])

	head.Left = insert(leftArr, head.Left)
	head.Right = insert(rightArr, head.Right)

	return head
}

func insert(nums []int, head *TreeNode) *TreeNode {
	if len(nums) == 0 {
		return nil
	}

	if len(nums) == 1 {
		return createNode(nums[0])
	}

	mid := len(nums) / 2

	leftArr := nums[:mid]
	rightArr := nums[mid+1:]

	head = createNode(nums[mid])

	head.Left = insert(leftArr, head.Left)
	head.Right = insert(rightArr, head.Right)

	return head
}

func createNode(val int) *TreeNode {
	return &TreeNode{Val: val, Left: nil, Right: nil}
}

Performance

• Runtime beats: 100%
• Memory beats: 77.88%

Complexity

• Time: O(n) Every node must be visited atleast once. Splitting the array, and creating the header are both constant operations.
• Space: O(n) Every array element becomes one node → n nodes → O(n) space. Depth is O(log n) for a balanced BST → O(log n) extra space. The array operation dominates. So O(n)