JavaScript Program to Convert Sorted Array to BST
Given a sorted array, convert it into a binary search tree (BST). A binary search tree is a binary tree where the value of each node is larger than the values in its left subtree and smaller than the values in its right subtree.
Example:
Input: sorted array= [2, 4, 7, 9, 10]
Output: Binary Search Tree
7
/ \
4 9
/ \
2 10
Below are different approaches to convert Sorted Array to BST in Javascript.
Table of Content
- Recursive Approach
- Iterative approach using Stack
Recursive Approach
In the recursive approach, we start by finding the middle element of the sorted array. This element becomes the root of the current subtree. We then recursively build the left subtree using the left part of the array and the right subtree using the right part of the array. This process continues until we have processed all elements of the array.
Example: This example uses recursive approach to convert Sorted Array to BST.
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function sortedArrayToBST(nums, start = 0, end = nums.length - 1) {
if (start > end) return null;
const mid = Math
.floor((start + end) / 2);
const root = new TreeNode(nums[mid]);
root
.left = sortedArrayToBST(nums, start, mid - 1);
root
.right = sortedArrayToBST(nums, mid + 1, end);
return root;
}
function inorderTraversal(node) {
if (node) {
inorderTraversal(node.left);
console.log(node.value);
inorderTraversal(node.right);
}
}
// Example usage
const nums = [2, 4, 7, 9, 10];
const root = sortedArrayToBST(nums);
// Print the BST
inorderTraversal(root);
Output
2 4 7 9 10
Time Complexity: O(n)
Space Complexity: O(n)
Iterative approach using Stack
In this approach, we are using a stack to iteratively build a binary search tree (BST) from a sorted array. We start by pushing an initial range representing the entire array onto the stack. Then, while the stack is not empty, we pop a range and create a node for the middle element of that range. If there are elements to the left or right of the middle element, we push new ranges for those subarrays onto the stack. This process continues until the stack is empty.
Example: This example uses stack to iteratively build a binary search tree from sorted array.
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function sortedArrayToBST(nums) {
if (!nums.length) return null;
const stack =
[
{
start: 0,
end: nums.length - 1,
parent: null,
isLeft: true
}
];
let root = null;
while (stack.length) {
const {
start,
end,
parent,
isLeft
} = stack
.pop();
const mid = Math
.floor((start + end) / 2);
const newNode = new TreeNode(nums[mid]);
if (!root) {
root = newNode;
}
if (parent) {
if (isLeft) parent
.left = newNode;
else parent
.right = newNode;
}
if (start < mid) {
stack.push
(
{
start,
end: mid - 1,
parent: newNode,
isLeft: true
}
);
}
if (end > mid) {
stack
.push
(
{
start: mid + 1,
end,
parent: newNode,
isLeft: false
}
);
}
}
return root;
}
function inorderTraversal(node) {
if (node) {
inorderTraversal(node.left);
console.log(node.value);
inorderTraversal(node.right);
}
}
// Example usage
const nums = [20, 40, 70, 90, 100];
const root = sortedArrayToBST(nums);
// Print the BST
inorderTraversal(root);
Output
2 4 7 9 10
Time Complexity: O(n)
Space Complexity: O(n).