Sorted Array to Balanced BST

Last Updated : 30 Mar, 2026

Given a sorted array arr[]. Convert it into a Balanced Binary Search Tree (BST). Return the root of the BST.

A Balanced Binary Search Tree (BST) is a type of binary tree in which the difference between the heights of the left and right subtrees of every node is at most one.

Examples: 

Input: arr[] = [10, 20, 30]
Output: [[20], [10, 30]]
Explanation: The above sorted array converted to below Balanced Binary Search Tree.

420046833

Input: arr[] = [1, 5, 9, 14, 23, 27]
Output: [[9], [1, 23], [N, 5, 14, 27]]
Explanation: The above sorted array converted to below Balanced Binary Search Tree.

7
Try it on GfG Practice
redirect icon

Table of Content

[Expected Approach - 1] Using Recursion - O(n) Time and O(n) Space

The idea is to use recursion to build the tree from a sorted array. We first find the middle element of the array and make it the root of the tree.
Then we recursively repeat the same process for the left subarray (to form the left subtree) and the right subarray (to form the right subtree). 

Why the Middle Element?
Choosing the middle element ensures that:

  • Half of the elements lie on the left side (smaller values)
  • Half of the elements lie on the right side (larger values)

This keeps the number of nodes in both subtrees as equal as possible, ensuring the tree remains height-balanced.

C++ 
//Driver Code Starts
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// Node structure
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int data) {
        this->data = data;
        left = right = nullptr;
    }
};


// Function to get Height
int getHeight(Node* root, int h) {
    if (root == nullptr) return h - 1;
    return max(getHeight(root->left, h + 1), getHeight(root->right, h + 1));
}

// Print level order
void levelOrder(Node* root) {
    queue<pair<Node*, int>> q;
    q.push({root, 0});

    int lastLevel = 0;

    // function to get the height of tree
    int height = getHeight(root, 0);

    // printing the level order of tree
    while (!q.empty()) {
        auto top = q.front(); q.pop();
        Node* node = top.first;
        int lvl = top.second;

        if (lvl > lastLevel) {
            cout << "
";
            lastLevel = lvl;
        }

        // all levels are printed
        if (lvl > height) break;

        
        if (node->data != -1) cout << node->data << " ";
        
        // printing null node
        else cout << "N ";

        // null node has no children
        if (node->data == -1) continue;

        if (node->left == nullptr) q.push({new Node(-1), lvl + 1});
        else q.push({node->left, lvl + 1});

        if (node->right == nullptr) q.push({new Node(-1), lvl + 1});
        else q.push({node->right, lvl + 1});
    }
}

// Recursive Function to Create BST
//Driver Code Ends

Node* sortedArrayToBSTRecur(vector<int>& arr, int start, int end) {
    if (start > end) return nullptr;

    int mid = start + (end - start) / 2;
    Node* root = new Node(arr[mid]);

    // Divide from middle element
    root->left = sortedArrayToBSTRecur(arr, start, mid - 1);
    root->right = sortedArrayToBSTRecur(arr, mid + 1, end);

    return root;
}

// Function which return BST
Node* sortedArrayToBST(vector<int>& arr) {
    return sortedArrayToBSTRecur(arr, 0, arr.size() - 1);
}


//Driver Code Starts

int main() {
    vector<int> arr = {1, 5, 9, 14, 23, 27};
    Node* root = sortedArrayToBST(arr);
    levelOrder(root);
    return 0;
}
//Driver Code Ends
Java 
//Driver Code Starts
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.LinkedList;

// Node strcuture
class Node {
    int data;
    Node left, right;
    
    Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

class GFG {
    
     // function to get height
    static int getHeight( Node root, int h ) {
        if( root == null ) return h-1;
        
        return Math.max(getHeight(root.left, h+1), getHeight(root.right, h+1));
    }
    
    // Print level order
    static void levelOrder(Node root) {
        Queue<List<Object>> queue = new LinkedList<>();
        queue.offer(List.of(root, 0));
        
        int lastLevel = 0;
        
        // function to get the height of tree
        int height = getHeight(root, 0);
        
        // printing the level order of tree
        while( !queue.isEmpty()) {
            List<Object> top = queue.poll();
            
            Node node = (Node) top.get(0);
            int lvl = (int) top.get(1);
            
            if( lvl > lastLevel ) {
                System.out.println();
                lastLevel = lvl;
            }
            
            // all levels are printed
            if( lvl > height ) break;
            
            // printing null node
            System.out.print((node.data == -1 ? "N" : node.data) + " ");
            
            // null node has no children
            if( node.data == -1 ) continue;
            
            if( node.left == null ) queue.offer(List.of(new Node(-1), lvl+1));
            else queue.offer(List.of(node.left, lvl+1));
            
            if( node.right == null ) queue.offer(List.of(new Node(-1), lvl+1));
            else queue.offer(List.of(node.right, lvl+1));
        }
    }
//Driver Code Ends

    
    // Recursive Function to Create BST
    static Node sortedArrayToBSTRecur(int[] arr, int start, int end) {
        if (start > end) return null;
    
        
        int mid = start + (end - start) / 2;
    
        Node root = new Node(arr[mid]);
    
        // Divide from middle element
        root.left = sortedArrayToBSTRecur(arr, start, mid - 1);
        root.right = sortedArrayToBSTRecur(arr, mid + 1, end);
    
        return root;
    }
    
    // Function which return BST
    static Node sortedArrayToBST(int[] arr) {
        return sortedArrayToBSTRecur(arr, 0, arr.length - 1);
    }
    

//Driver Code Starts

    public static void main(String[] args) {
        int[] arr = {1, 5, 9, 14, 23, 27};
        Node root = sortedArrayToBST(arr);
        
        levelOrder(root);
    }
}

//Driver Code Ends
Python 
#Driver Code Starts
from collections import deque

# Node structure
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# function to get height
def getHeight(root, h):
    if root is None:
        return h - 1
    return max(getHeight(root.left, h + 1), getHeight(root.right, h + 1))


# Print level order
def levelOrder(root):
    queue = deque([[root, 0]])
    lastLevel = 0

    # function to get the height of tree
    height = getHeight(root, 0)

    # printing the level order of tree
    while queue:
        node, lvl = queue.popleft()

        if lvl > lastLevel:
            print()
            lastLevel = lvl

        # all levels are printed
        if lvl > height:
            break

        # printing null node
        print("N" if node.data == -1 else node.data, end=" ")

        # null node has no children
        if node.data == -1:
            continue

        if node.left is None:
            queue.append([Node(-1), lvl + 1])
        else:
            queue.append([node.left, lvl + 1])

        if node.right is None:
            queue.append([Node(-1), lvl + 1])
        else:
            queue.append([node.right, lvl + 1])

#Driver Code Ends


# Recursive Function to Create BST
def sortedArrayToBSTRecur(arr, start, end):
    if start > end:
        return None

    mid = start + (end - start) // 2
    root = Node(arr[mid])

    # Divide from middle element
    root.left = sortedArrayToBSTRecur(arr, start, mid - 1)
    root.right = sortedArrayToBSTRecur(arr, mid + 1, end)

    return root

# Function which return BST
def sortedArrayToBST(arr):
    return sortedArrayToBSTRecur(arr, 0, len(arr) - 1)




#Driver Code Starts
if __name__ == "__main__":
    arr = [1, 5, 9, 14, 23, 27]
    root = sortedArrayToBST(arr)
    levelOrder(root)
#Driver Code Ends
C# 
//Driver Code Starts
using System;
using System.Collections.Generic;

// Node structure
class Node {
    public int data;
    public Node left, right;

    public Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

class GFG {
        static int GetHeight(Node root, int h) {
        if (root == null) return h - 1;
        return Math.Max(GetHeight(root.left, h + 1), GetHeight(root.right, h + 1));
    }

    static void levelOrder(Node root) {
        Queue<(Node, int)> queue = new Queue<(Node, int)>();
        queue.Enqueue((root, 0));

        int lastLevel = 0;

        // function to get the height of tree
        int height = GetHeight(root, 0);

        // printing the level order of tree
        while (queue.Count > 0) {
            var (node, lvl) = queue.Dequeue();

            if (lvl > lastLevel) {
                Console.WriteLine();
                lastLevel = lvl;
            }

            // all levels are printed
            if (lvl > height) break;

            // printing null node
            Console.Write((node.data == -1 ? "N" : node.data.ToString()) + " ");

            // null node has no children
            if (node.data == -1) continue;

            if (node.left == null) queue.Enqueue((new Node(-1), lvl + 1));
            else queue.Enqueue((node.left, lvl + 1));

            if (node.right == null) queue.Enqueue((new Node(-1), lvl + 1));
            else queue.Enqueue((node.right, lvl + 1));
        }
    }

//Driver Code Ends


    // Recursive Function to Create BST
    static Node sortedArrayToBSTRecur(int[] arr, int start, int end) {
        if (start > end) return null;

        int mid = start + (end - start) / 2;

        Node root = new Node(arr[mid]);

        // Divide from middle element
        root.left = sortedArrayToBSTRecur(arr, start, mid - 1);
        root.right = sortedArrayToBSTRecur(arr, mid + 1, end);

        return root;
    }

    // Recursive Function to Create BST
    static Node sortedArrayToBST(int[] arr) {
        return sortedArrayToBSTRecur(arr, 0, arr.Length - 1);
    }
    

//Driver Code Starts
    static void Main() {
        int[] arr = { 1, 5, 9, 14, 23, 27 };
        Node root = sortedArrayToBST(arr);
        levelOrder(root);
    }
}
//Driver Code Ends
JavaScript 
//Driver Code Starts
// Node structure
class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

// Custom Queue Implementation
class Queue {
    constructor() {
        this.items = {};
        this.headIndex = 0;
        this.tailIndex = 0;
    }

    enqueue(item) {
        this.items[this.tailIndex] = item;
        this.tailIndex++;
    }

    dequeue() {
        if (this.isEmpty()) return null;
        let item = this.items[this.headIndex];
        delete this.items[this.headIndex];
        this.headIndex++;
        return item;
    }

    isEmpty() {
        return this.tailIndex === this.headIndex;
    }

    size() {
        return this.tailIndex - this.headIndex;
    }
}

function getHeight(root, h) {
    if (root === null) return h - 1;
    return Math.max(getHeight(root.left, h + 1), getHeight(root.right, h + 1));
}

function levelOrder(root) {
    let q = new Queue();
    q.enqueue([root, 0]);

    let lastLevel = 0;

    // function to get the height of tree
    let height = getHeight(root, 0);

    // printing the level order of tree
    while (!q.isEmpty()) {
        let [node, lvl] = q.dequeue();

        if (lvl > lastLevel) {
            console.log("");
            lastLevel = lvl;
        }

        // all levels are printed
        if (lvl > height) break;

        // printing null node
        process.stdout.write((node.data === -1 ? "N" : node.data) + " ");

        // null node has no children
        if (node.data === -1) continue;

        if (node.left === null) q.enqueue([new Node(-1), lvl + 1]);
        else q.enqueue([node.left, lvl + 1]);

        if (node.right === null) q.enqueue([new Node(-1), lvl + 1]);
        else q.enqueue([node.right, lvl + 1]);
    }
}
//Driver Code Ends


// Recursive Function to Create BST
function sortedArrayToBSTRecur(arr, start, end) {
    if (start > end) return null;

    let mid = start + Math.floor((end - start) / 2);
    let root = new Node(arr[mid]);

    // Divide from middle element
    root.left = sortedArrayToBSTRecur(arr, start, mid - 1);
    root.right = sortedArrayToBSTRecur(arr, mid + 1, end);

    return root;
}

// Function which return BST
function sortedArrayToBST(arr) {
    return sortedArrayToBSTRecur(arr, 0, arr.length - 1);
}

// Driver code

//Driver Code Starts
const arr = [1, 5, 9, 14, 23, 27];
const root = sortedArrayToBST(arr);
levelOrder(root);
//Driver Code Ends

Output
9 
1 23 
N 5 14 27

[Expected Approach - 2] Using queue - O(n) Time and O(n) Space

The idea is to traverse the tree in level order manner, starting from root node. Check for each node, if left subtree exists, then create the left node and push it into queue. Similarly, if right subtree exists, then create the right node and push it into queue.

Step-by-step approach:

  • Initialize a queue with the root node (middle of array) and its range [0, n-1].
  • While the queue isn’t empty:
    Pop the front node with its [start, end] range.
    Find mid = (start + end) / 2.
    If start < mid, create the left child using the middle of [start, mid-1], link it, and push it with its range.
    If end > mid, create the right child using the middle of [mid+1, end], link it, and push it with its range.
  • Return the root.
C++ 
//Driver Code Starts
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

// Node structure
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int data) {
        this->data = data;
        left = right = nullptr;
    }
};

int getHeight(Node* root, int h) {
    if (root == nullptr) return h - 1;
    return max(getHeight(root->left, h + 1), getHeight(root->right, h + 1));
}


void levelOrder(Node* root) {
    queue<pair<Node*, int>> q;
    q.push({root, 0});

    int lastLevel = 0;

    // function to get the height of tree
    int height = getHeight(root, 0);

    // printing the level order of tree
    while (!q.empty()) {
        auto [node, lvl] = q.front();
        q.pop();

        if (lvl > lastLevel) {
            cout << "
";
            lastLevel = lvl;
        }

        // all levels are printed
        if (lvl > height) break;

        // printing null node
        if (node->data != -1) cout << node->data << " ";
        else cout << "N ";

        // null node has no children
        if (node->data == -1) continue;

        if (node->left == nullptr) q.push({new Node(-1), lvl + 1});
        else q.push({node->left, lvl + 1});

        if (node->right == nullptr) q.push({new Node(-1), lvl + 1});
        else q.push({node->right, lvl + 1});
    }
}
//Driver Code Ends


// helper class to store {node, start, end}
class Data {
public:
    Node* node;
    int start, end;
    Data(Node* node, int start, int end) {
        this->node = node;
        this->start = start;
        this->end = end;
    }
};

Node* sortedArrayToBST(vector<int>& arr) {
    int n = arr.size();
    if (n == 0) return nullptr;

    int mid = (n - 1) / 2;
    Node* root = new Node(arr[mid]);

    queue<Data> q;
    q.push(Data(root, 0, n - 1));

    while (!q.empty()) {
        Data d = q.front(); q.pop();
        Node* curr = d.node;
        int st = d.start, en = d.end;
        mid = (st + en) / 2;

        // if left subtree exists
        if (st < mid) {
            int leftVal = (st + mid - 1) / 2;
            Node* left = new Node(arr[leftVal]);
            curr->left = left;
            q.push(Data(left, st, mid - 1));
        }

        // if right subtree exists
        if (en > mid) {
            int rightVal = (mid + 1 + en) / 2;
            Node* right = new Node(arr[rightVal]);
            curr->right = right;
            q.push(Data(right, mid + 1, en));
        }
    }

    return root;
}


//Driver Code Starts
int main() {
    vector<int> arr = {1, 5, 9, 14, 23, 27};
    Node* root = sortedArrayToBST(arr);
    levelOrder(root);
    return 0;
}
//Driver Code Ends
Java 
//Driver Code Starts
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.LinkedList;

// Node structure
class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}


class Print{
        
        public int getHeight( Node root, int h ) {
            if( root == null ) return h-1;
            
            return Math.max(getHeight(root.left, h+1), getHeight(root.right, h+1));
        }

        public void levelOrder(Node root) {
        Queue<List<Object>> queue = new LinkedList<>();
        queue.offer(List.of(root, 0));
        
        int lastLevel = 0;
        
        // function to get the height of tree
        int height = getHeight(root, 0);
        
        // printing the level order of tree
        while( !queue.isEmpty()) {
            List<Object> top = queue.poll();
            
            Node node = (Node) top.get(0);
            int lvl = (int) top.get(1);
            
            if( lvl > lastLevel ) {
                System.out.println();
                lastLevel = lvl;
            }
            
            // all levels are printed
            if( lvl > height ) break;
            
            // printing null node
            System.out.print((node.data == -1 ? "N" : node.data) + " ");
            
            // null node has no children
            if( node.data == -1 ) continue;
            
            if( node.left == null ) queue.offer(List.of(new Node(-1), lvl+1));
            else queue.offer(List.of(node.left, lvl+1));
            
            if( node.right == null ) queue.offer(List.of(new Node(-1), lvl+1));
            else queue.offer(List.of(node.right, lvl+1));
        }
    }

}
//Driver Code Ends


// helper class to store {node, start, end}
class Data {
    Node node;
    int start, end;

    Data(Node node, int start, int end) {
        this.node = node;
        this.start = start;
        this.end = end;
    }
}

class GFG {

    static Node sortedArrayToBST(int[] arr) {
        int n = arr.length;

        if (n == 0)
            return null;

        // create the root node.
        int mid = (n - 1) / 2;
        Node root = new Node(arr[mid]);

        Queue<Data> q = new LinkedList<>();
        q.add(new Data(root, 0, n - 1));

        while (!q.isEmpty()) {
            Data d = q.poll();

            Node curr = d.node;
            int st = d.start, en = d.end;
            mid = (st + en)/2;

            // if left subtree exists
            if (st < mid) {
                int leftVal = (st + mid - 1) / 2;
                Node left = new Node(arr[leftVal]);
                curr.left = left;
                q.add(new Data(left, st, mid - 1));
            }

            // if right subtree exists
            if (en > mid) {
                int rightVal = (mid + 1 + en)/2;
                Node right = new Node(arr[rightVal]);
                curr.right = right;
                q.add(new Data(right, mid + 1, en));
            }
        }

        return root;
    }
    

//Driver Code Starts

    public static void main(String[] args) {
        int[] arr = { 1, 5, 9, 14, 23, 27 };
        Node root = sortedArrayToBST(arr);
        Print print = new Print();
        print.levelOrder(root);
    }
}
//Driver Code Ends
Python 
#Driver Code Starts
from collections import deque

# Node structure
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def getHeight(root, h):
    if root is None:
        return h - 1
    return max(getHeight(root.left, h + 1), getHeight(root.right, h + 1))


def levelOrder(root):
    queue = deque([[root, 0]])
    lastLevel = 0

    # function to get the height of tree
    height = getHeight(root, 0)

    # printing the level order of tree
    while queue:
        node, lvl = queue.popleft()

        if lvl > lastLevel:
            print()
            lastLevel = lvl

        # all levels are printed
        if lvl > height:
            break

        # printing null node
        print("N" if node.data == -1 else node.data, end=" ")

        # null node has no children
        if node.data == -1:
            continue

        if node.left is None:
            queue.append([Node(-1), lvl + 1])
        else:
            queue.append([node.left, lvl + 1])

        if node.right is None:
            queue.append([Node(-1), lvl + 1])
        else:
            queue.append([node.right, lvl + 1])

#Driver Code Ends


# helper class to store {node, start, end}
class Data:
    def __init__(self, node, start, end):
        self.node = node
        self.start = start
        self.end = end

def sortedArrayToBST(arr):
    n = len(arr)
    if n == 0:
        return None

    mid = (n - 1) // 2
    root = Node(arr[mid])

    q = deque([Data(root, 0, n - 1)])

    while q:
        d = q.popleft()
        curr = d.node
        st, en = d.start, d.end
        mid = (st + en) // 2

        # if left subtree exists
        if st < mid:
            leftVal = (st + mid - 1) // 2
            left = Node(arr[leftVal])
            curr.left = left
            q.append(Data(left, st, mid - 1))

        # if right subtree exists
        if en > mid:
            rightVal = (mid + 1 + en) // 2
            right = Node(arr[rightVal])
            curr.right = right
            q.append(Data(right, mid + 1, en))

    return root


#Driver Code Starts
if __name__ == "__main__":
    arr = [1, 5, 9, 14, 23, 27]
    root = sortedArrayToBST(arr)
    levelOrder(root)

#Driver Code Ends
C# 
//Driver Code Starts
using System;
using System.Collections.Generic;

// Node structure
class Node {
    public int data;
    public Node left, right;

    public Node(int data) {
        this.data = data;
        this.left = this.right = null;
    }
}

class Print {
      public int GetHeight(Node root, int h) {
        if (root == null) return h - 1;
        return Math.Max(GetHeight(root.left, h + 1), GetHeight(root.right, h + 1));
    }

    public void levelOrder(Node root) {
        Queue<(Node, int)> queue = new Queue<(Node, int)>();
        queue.Enqueue((root, 0));

        int lastLevel = 0;

        // function to get the height of tree
        int height = GetHeight(root, 0);

        // printing the level order of tree
        while (queue.Count > 0) {
            var (node, lvl) = queue.Dequeue();

            if (lvl > lastLevel) {
                Console.WriteLine();
                lastLevel = lvl;
            }

            // all levels are printed
            if (lvl > height) break;

            // printing null node
            Console.Write((node.data == -1 ? "N" : node.data.ToString()) + " ");

            // null node has no children
            if (node.data == -1) continue;

            if (node.left == null) queue.Enqueue((new Node(-1), lvl + 1));
            else queue.Enqueue((node.left, lvl + 1));

            if (node.right == null) queue.Enqueue((new Node(-1), lvl + 1));
            else queue.Enqueue((node.right, lvl + 1));
        }
    }

}
//Driver Code Ends


// helper class to store {node, start, end}
class Data {
    public Node node;
    public int start, end;

    public Data(Node node, int start, int end) {
        this.node = node;
        this.start = start;
        this.end = end;
    }
}

class GFG {
    
    static Node sortedArrayToBST(int[] arr) {
        int n = arr.Length;
        if (n == 0) return null;

        int mid = (n - 1) / 2;
        Node root = new Node(arr[mid]);

        Queue<Data> q = new Queue<Data>();
        q.Enqueue(new Data(root, 0, n - 1));

        while (q.Count > 0) {
            Data d = q.Dequeue();
            Node curr = d.node;
            int st = d.start, en = d.end;
            mid = (st + en) / 2;

            // if left subtree exists
            if (st < mid) {
                int leftVal = (st + mid - 1) / 2;
                Node left = new Node(arr[leftVal]);
                curr.left = left;
                q.Enqueue(new Data(left, st, mid - 1));
            }

            // if right subtree exists
            if (en > mid) {
                int rightVal = (mid + 1 + en) / 2;
                Node right = new Node(arr[rightVal]);
                curr.right = right;
                q.Enqueue(new Data(right, mid + 1, en));
            }
        }

        return root;
    }


//Driver Code Starts
    static void Main() {
        int[] arr = { 1, 5, 9, 14, 23, 27 };
        Node root = sortedArrayToBST(arr);
        Print print = new Print();
        print.levelOrder(root);
    }
}

//Driver Code Ends
JavaScript 
//Driver Code Starts
// Node structure
class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

// Custom Queue Implementation
class Queue {
    constructor() {
        this.items = {};
        this.headIndex = 0;
        this.tailIndex = 0;
    }

    enqueue(item) {
        this.items[this.tailIndex] = item;
        this.tailIndex++;
    }

    dequeue() {
        if (this.isEmpty()) return null;
        let item = this.items[this.headIndex];
        delete this.items[this.headIndex];
        this.headIndex++;
        return item;
    }

    isEmpty() {
        return this.tailIndex === this.headIndex;
    }

    size() {
        return this.tailIndex - this.headIndex;
    }
}

function getHeight(root, h) {
    if (root === null) return h - 1;
    return Math.max(getHeight(root.left, h + 1), getHeight(root.right, h + 1));
}

function levelOrder(root) {
    let q = new Queue();
    q.enqueue([root, 0]);

    let lastLevel = 0;

    // function to get the height of tree
    let height = getHeight(root, 0);

    // printing the level order of tree
    while (!q.isEmpty()) {
        let [node, lvl] = q.dequeue();

        if (lvl > lastLevel) {
            console.log("");
            lastLevel = lvl;
        }

        // all levels are printed
        if (lvl > height) break;

        // printing null node
        process.stdout.write((node.data === -1 ? "N" : node.data) + " ");

        // null node has no children
        if (node.data === -1) continue;

        if (node.left === null) q.enqueue([new Node(-1), lvl + 1]);
        else q.enqueue([node.left, lvl + 1]);

        if (node.right === null) q.enqueue([new Node(-1), lvl + 1]);
        else q.enqueue([node.right, lvl + 1]);
    }
}
//Driver Code Ends


// helper object to store {node, start, end}
class Data {
    constructor(node, start, end) {
        this.node = node;
        this.start = start;
        this.end = end;
    }
}

function sortedArrayToBST(arr) {
    let n = arr.length;
    if (n === 0) return null;

    let mid = Math.floor((n - 1) / 2);
    let root = new Node(arr[mid]);

    let q = new Queue();
    q.enqueue(new Data(root, 0, n - 1));

    while (!q.isEmpty()) {
        let d = q.dequeue();
        let curr = d.node;
        let st = d.start, en = d.end;
        mid = Math.floor((st + en) / 2);

        // if left subtree exists
        if (st < mid) {
            let leftVal = Math.floor((st + mid - 1) / 2);
            let left = new Node(arr[leftVal]);
            curr.left = left;
            q.enqueue(new Data(left, st, mid - 1));
        }

        // if right subtree exists
        if (en > mid) {
            let rightVal = Math.floor((mid + 1 + en) / 2);
            let right = new Node(arr[rightVal]);
            curr.right = right;
            q.enqueue(new Data(right, mid + 1, en));
        }
    }

    return root;
}


//Driver Code Starts
// Driver code
const arr = [1, 5, 9, 14, 23, 27];
const root = sortedArrayToBST(arr);
levelOrder(root);

//Driver Code Ends

Output
9 
1 23 
N 5 14 27
Comment

Explore