Balanced BST From a Sorted Array - Iterative Approach

Question

I want to create a balanced BST from a sorted array iteratively. I understand how to create this BST recursively, but how would you go about doing this iteratively? assuming a Node in the tree has left,right child and a parent.

I tried implementing the same key idea as in the recursive solution (take the median to be the root at each iteration). got stuck pretty fast when trying to write the for loop. saw some ideas about stack or queue but could not understand why you must create one of these (maybe you don't).Also in general why does iterative solution seem to be way more complicated than the recursive one? (and also not popular) could use help. (jave please if you supply code)

*I'm a beginner (don't be to harsh :))

Answer 1

You can use an iterative approach where you target a tree that is complete, i.e. where the leaves are all on the bottom two levels, and the bottom level has all its nodes at the left side of that level.

From the size of the input array you can calculate what the height is of the tree to build and how many nodes will be in its bottom level.

Then you can use an array where each index corresponds to a level, and each entry represents the rightmost node in that level (if relevant). This array will start out will all null entries, and the first entry to get a Node instance will be its last entry (at the end of the array), because it will be a leaf. With some logic you can know at which level the next node will end up, store its reference at that index in the array, and link it up with its child (if any).

Here is an implementation with some comments explaining some details:

Node

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

BinarySearchTree

import java.util.*;

class BinarySearchTree {
    Node root = null;
    
    BinarySearchTree(int[] values) {
        if (values.length == 0) return;
        int height = (int)(Math.log(values.length) / Math.log(2));
        // Number of nodes to be placed in the bottom level of the new tree:
        int bottomCount = (values.length + 1) - (1 << height);
        Node path[] = new Node[height + 1];
        Arrays.fill(path, null);
        // Depth that the next node will have in the new tree 
        int depth = height; 
        for (int value : values) {
            path[depth] = new Node(value);
            // Is there a left child to link?
            if (depth + 1 < path.length && path[depth+1] != null) { 
                path[depth].left = path[depth+1];
                path[depth+1] = null;
            }
            if (depth < height) {
                depth = height; // Next node will be a leaf
            } else {
                // Has bottom level been covered? 
                //    Then remaining part has one less level
                if (--bottomCount == 0) height--;
                while (depth-- > 0 && path[depth] != null) {
                    path[depth].right = path[depth+1];
                    path[depth+1] = null;
                }
            }
        }
        root = path[0];
    }

    void print() {
        print(root, "");
    }

    void print(Node node, String indent) {
        if (node == null) return;
        print(node.right, indent + "   ");
        System.out.println(indent + node.value);
        print(node.left, indent + "   ");
    }
}

Driver code

    public static void main(String[] args) {
        int values[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        BinarySearchTree tree = new BinarySearchTree(values);
        tree.print();
    }

This has O(n) time complexity, and O(logn) auxiliary space complexity (not counting input -- the array of values -- nor output -- the tree).

Answer 2

To create a balanced binary search tree (BST) from a sorted array iteratively, you can use a technique called the "Bottom-Up" approach. Here's how you can do it:

1. Initialize an empty stack. This stack will store pairs of indices representing the range of elements for each subtree.

2. Push the initial range [0, n-1] onto the stack, where n is the size of the sorted array.

3. While the stack is not empty, do the following:

   • Pop the top pair of indices from the stack. Let's call them start and end.

   • Calculate the middle index as mid = (start + end) // 2.

   • Create a new node with the value at index mid in the sorted array.

   • Set the left child of the new node to the result of the next iteration with the range [start, mid-1] (i.e., the left half of the current range).

   • Set the right child of the new node to the result of the next iteration with the range [mid+1, end] (i.e., the right half of the current range).

   • Set the parent of the new node as needed.

4. Return the root of the BST.

example code:

class Node {
int value;
Node left;
Node right;
Node parent;

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

}
public class BalancedBST {
    public static Node createBalancedBSTIterative(int[] sortedArray) {
        int n = sortedArray.length;
        if (n == 0) {
            return null;
        }

    Stack<int[]> stack = new Stack<>();
    Node root = null;

    int start = 0;
    int end = n - 1;

    int mid = (start + end) / 2;
    root = new Node(sortedArray[mid]);
    stack.push(new int[]{start, mid - 1});
    stack.push(new int[]{mid + 1, end});

    while (!stack.empty()) {
        int[] range = stack.pop();
        start = range[0];
        end = range[1];
        mid = (start + end) / 2;

        Node parent = new Node(sortedArray[mid]);
        parent.parent = root;

        if (start <= mid - 1) {
            stack.push(new int[]{start, mid - 1});
            parent.left = new Node(0);  // Placeholder node for now
        }

        if (mid + 1 <= end) {
            stack.push(new int[]{mid + 1, end});
            parent.right = new Node(0); // Placeholder node for now
        }

        if (parent.parent != null) {
            if (parent == parent.parent.left) {
                parent.parent.left = parent;
            } else {
                parent.parent.right = parent;
            }
        } else {
            root = parent;
        }
    }

    return root;
}

public static void main(String[] args) {
    int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    Node root = createBalancedBSTIterative(sortedArray);
    // You can traverse and print the resulting tree to verify the correctness
}
}

Answer 3

Why is it "complicated" ?

Because if you update the nodes to the tree in sorted order, you access the nodes following varying paths in the tree, of varying lengths. To manage these paths, you need an auxiliary data structure.

E.g.

          3
      1       5
    0   2   4   6

The nodes are filled using the successive paths

3 1 0
3 1
3 1 2
3
3 5 4
3 5
3 5 6