Balanced BST From a Sorted Array - Iterative Approach

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 :))

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).