Building balanced BST from sorted array: recursive and iterative approaches I am implementing an algorithm to solve the following problem:


  Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.


The solution of this problem using recursion is quite straightforward:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def build_bst_recursive(array):
    size = len(array)
    return _build_bst(array, first=0, last=size - 1)


def _build_bst(array, first, last):
    if last &lt; first:
        return None
    mid = (first + last) // 2
    node = Node(mid)
    node.left = _build_bst(array, first, mid - 1)
    node.right = _build_bst(array, mid + 1, last)
    return node


Out of curiosity I also would like to solve the same problem using an iterative algorithm. Here is what I came up with:

class Stack:
    class _Node:
        def __init__(self, value):
            self.value = value
            self.next_node = None

    def __init__(self):
        self.head_node = None

    def is_empty(self):
        return self.head_node is None

    def push(self, value):
        node = self._Node(value)
        node.next_node = self.head_node
        self.head_node = node

    def pop(self):
        if self.is_empty():
            raise Exception("Stack is empty.")
        node = self.head_node
        self.head_node = node.next_node
        return node.value

def build_bst_iterative(array):
    size = len(array)

    # Stack stores tuples of the first and the last indices of half-segments:
    stack_indices = Stack()
    stack_indices.push((0, size - 1))

    # Stack stores tree nodes:
    stack_nodes = Stack()

    # Add to the stack a node that will be a root of the tree:
    root_node = Node(None)
    stack_nodes.push(root_node)

    while not stack_indices.is_empty():
        first, last = stack_indices.pop()
        node = stack_nodes.pop()

        if last &lt; first:
            # The segment is degenerated. Keep the node empty.
            continue
        elif last == first:
            # Assign the value, it is the last bottom node.
            node.value = array[last]
            continue

        mid = (first + last) // 2
        node.value = array[mid]
        node.left = Node(None)
        node.right = Node(None)

        # Update stacks:
        # (right half-segment)
        stack_indices.push((mid + 1, last))
        stack_nodes.push(node.right)
        # (left half-segment)
        stack_indices.push((first, mid - 1))
        stack_nodes.push(node.left)
    assert stack_nodes.is_empty()

    return root_node


I would highly appreciate if you could review the code and suggest any approaches for improvement. For example, I am trying to understand if it is possible to use only one stack.

EDIT After looking into my code in the morning, I realise that there is no need for two stacks because I always push and pop to the two stacks at the same time. Here there is an updated version of the code:

def build_bst_iterative_one_stack(array):
    size = len(array)

    # Add to the stack a node that will be a root of the tree:
    root_node = Node(None)

    # Stack stores tuples of the current node, and the first and the last indices of half-segments:
    stack = Stack()
    stack.push((root_node, 0, size - 1))

    while not stack.is_empty():
        node, first, last = stack.pop()

        if last &lt; first:
            # The segment is degenerated. Do nothing.
            continue
        elif last == first:
            # Assign the value, it is the last bottom node.
            node.value = array[last]
            continue

        mid = (first + last) // 2
        node.value = array[mid]
        node.left = Node(None)
        node.right = Node(None)

        # Update the stack with the left and the right half-segment:
        stack.push((node.right, mid + 1, last))
        stack.push((node.left, first, mid - 1))
    assert stack.is_empty()

    return root_node
Let me start with an all too common hindsight:
your code lacks test support and scaffold.

The most basic test support for a class is a succinct __str__, for class Node:

def __str__(self):
    return '&lt;' + ('.' if not self.left else (str(self.left) + '|')) \
        + str(self.value) + ('.' if not self.right
                             else ('|' + str(self.right))) + '&gt;'


(a more elaborate one would allow to limit recursion.) The result for

if __name__ == '__main__':
    ascending = [chr(x) for x in range(ord('a'), ord('g'))]
    print(build_bst_recursive(ascending))
    print(build_bst_iterative_one_stack(ascending))



  &lt;&lt;.0|&lt;.1.>>|2|&lt;&lt;.3.>|4|&lt;.5.>>>
  &lt;&lt;&lt;.None.>|a|&lt;.b.>>|c|&lt;&lt;.d.>|e|&lt;.f.>>>


highlights an oversight with _build_bst() (not using node = Node(array[mid])) and a problem in the stack variants with always creating two child nodes (or with the handling commented # The segment is degenerated. Do nothing.).  



Your code is more or less in line with the Style Guide for Python Code (good - do you use an IDE, your IDE's PEP8 support?); make it a habit to provide documentation strings for everything public, too.  

If I was serious about comparing alternative implementations, I'd try to define an interface and hope to avoid names like build_bst_iterative_one_stack.
I got used to the builtin len(), I don't see an advantage to introducing size = len(array) where used once.

_build_bst() is pretty basic; if it was public, it would need a doc string specifying last to be inclusive. I don't like the name array - would prefer values or ordered (ascending would be misleading, as _build_bst() works perfectly for descending values).

I'd hesitate to roll my own stack class, more so if the stated purpose was something else, entirely. If I did, I'd just extend list:

class Stack(list):
    ''' syntactic sugar: adds push(), is_empty() to list's pop() '''
    push = list.append

    def is_empty(self):
        return not bool(self)


(Skipping build_bst_iterative().)
In build_bst_iterative_one_stack(), I'd prefer toDo over stack. The comment stack stores […and…] indices of half-segments is funny in the first tuple pushed two statements down not being a half.
I don't have an inspiration how to fix the introduction of None-Nodes without duplicating the check.

Your "build_bst_iterative*()" implementations are straightforward conversions of the basic recursive approach (see Create Balanced Binary Search Tree from Sorted linked list for one working without "random" access); I would not expect insights beyond doesn't get prettier for explicit stack handling.  

Much to my dismay, I didn't find a decent web reference for a genuine iterative approach (numerous weird ones, some as new as 2019/3/2):
First consider the case of 2ⁿ-1 nodes: with levels numbered from 0 for bottom (up to n-1), the level of each node is the number of trailing zeroes in its ordinal. Have an array to reference one node for each level, initialised to Nones. For each value, create a Node. Check the reference at the level indicated by the number of trailing zeroes in its ordinal: if None, just plant the node there and make whatever is one level lower its left descendant. If not None, make node the right descendant of the node at the next higher level an set this level to None. (As an alternative to checking this reference, you can inspect the bit in the ordinal just two above the trailing zeroes.)
There are numerous ways to handle N ≠ 2ⁿ-1; one being to aim for a complete binary tree: compute the ordinal rb of the rightmost node at the bottom level. Proceed as above to rb+1, and increase the "ordinal number" by two instead of one thereafter.
(Finally, return the node at the highest level as the root of the tree built…)