Sorted Array and BST Conversion

Binary Search Tree is a sorted binary tree. Construct a BST from a sorted array by finding the middle element of the sorted array as root and recursively implementing the same operation on the left and right subtree. On the other hand, perform in-order traversal on the BST to build an array in ascending order.

sorted array and BST conversion summary card

Table of Contents
· Binary Search Tree(BST)
· Convert Sorted Array to BST
  ∘ Graphical Explanation
· Convert BST to Sorted Array
  ∘ Graphical Explanation
· Code Implementation
  ∘ Complexity
  ∘ Golang
  ∘ Python

Binary Search Tree(BST)

A binary search tree is a sorted binary tree. Every node in the tree follow a specific ordering property:

# unique values
key: left subtree < node < right subtree
# duplicate values(depend on the problem's definition)
key: left subtree <= node < right subtree
or 
key: left subtree < node <= right subtree

binary search tree

Convert Sorted Array to BST

LeetCode 108: Convert Sorted Array to Binary Search Tree

The approach works by picking the middle element in the sorted array as root for the binary tree. Then, recursively implement the same operation on the left and right subtree.

Graphical Explanation

sorted array

• step1: calculate the middle index of the sorted array

midIdx = floor((startIdx + endIdx)/2)

• step2: set the middle element as root
• step3: recursively implement step1 and step2 on the left subtree and right subtree

startIdx to midIdx - 1 --> left subtree
midIdx + 1 to endIdx --> right subtree

1 and 2

3 and 4

5 and 6

7 and 8

9

Convert BST to Sorted Array

Perform in-order traversal on the BST to visit nodes in ascending order.

Graphical Explanation

BST

process

Code Implementation

Complexity

• Convert Sorted Array to BST
  Time: O(n)
  Space: O(n)
  n: the total number of elements in the given array
• Convert BST to Sorted Array
  Time: O(n)
  Space: O(n)
  n: the total number of elements in the given array

Golang

Python

You can access the source code here.

LeetCode Problem:

Convert Sorted Array to Binary Search Tree - LeetCode