4
\$\begingroup\$

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 < 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 < 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 < 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
\$\endgroup\$
  • \$\begingroup\$ (The second thing striking about the iterative approach is the roll-your-own stack - what's wrong with list.append/pop? The sole reason I tried to understand that non-commented code was that I was curious whether you presented a bottom-up procedure.) \$\endgroup\$ – greybeard Mar 7 at 7:23
  • \$\begingroup\$ @greybeard thank you for your comment. You are right I could use a list. I also added some comments to make the iterative algorithm easier to understand. In a bottom-up procedure you would build tree from bottom? In this case I have a top-down procedure. I would highly appreciate if you could elaborate how to implement a bottom-up procedure. Also, what is also the first thing striking about the iterative approach? \$\endgroup\$ – desa Mar 7 at 9:06
  • \$\begingroup\$ (I was about to compliment you on your post when I found part of the praise would have to go to 200_success - in my eyes, you didn't do half bad as it is.) (Note that changes to the code are not welcome once reviews started.) \$\endgroup\$ – greybeard Mar 7 at 10:47
  • \$\begingroup\$ @greybeard (ok, probably I miss something about what 200_success wrote.) (Thanks for telling me about the code changes, I didn't know about this. Just joined the community.) \$\endgroup\$ – desa Mar 7 at 11:46
  • 1
    \$\begingroup\$ (See also: Create Balanced Binary Search Tree from Sorted linked list) \$\endgroup\$ – greybeard Mar 7 at 13:58
2
\$\begingroup\$

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 '<' + ('.' if not self.left else (str(self.left) + '|')) \
        + str(self.value) + ('.' if not self.right
                             else ('|' + str(self.right))) + '>'

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

<<.0|<.1.>>|2|<<.3.>|4|<.5.>>>
<<<.None.>|a|<.b.>>|c|<<.d.>|e|<.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…)

\$\endgroup\$
  • \$\begingroup\$ Thank you a lot for your review! (I use PyCharm and you can configure github.com/ambv/black to format the code on save or on shortcut) (I also didn't yet come up with a strategy how to overcome the introduction of None-Nodes...) (Special thanks for the link that you provided about how to implement the algorithm for SLL. It is really useful to see how you can do it with in-place traversal!) (Wow I am quite surprised that I came up with a question that brings us to very recent publications in the field.) Thank you again for your time, reading your review was really useful. \$\endgroup\$ – desa Mar 7 at 15:52
  • \$\begingroup\$ @desa: on the CR help page on asking questions, there is one What should I do when someone answers my question? - see the paragraph about I improved my code…. (My take on accepting an answer has shifted to allow two days before accepting an answer (the good news being that you can shift the accept to a different answer).) \$\endgroup\$ – greybeard Mar 7 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.