Code showing the algorithm for Constant space, Linear Time In-Order Traversal of a Binary Tree stored in an Array in Heap Order

ConstantSpaceInOrderTraversalBSTArrayRepresentation.py

def fill_inorder_recursive_bst_array(bst, idx, val):
    """Recursively fill an array "bst" with values so that values
    increment by 1 every time. "idx" is the index in "bst" that
    the method should look up to write out the next value in sequence.

    The first invocation is expected to pass idx == 0, with enough
    space in the BST array (bst) to hold a complete and balanced
    binary tree.

    This method returns the next value in sequence that need to be
    written to "bst" by the caller (parent call).
    """
    if idx*2 + 1 < len(bst):
        val = fill_inorder_recursive_bst_array(bst, idx*2 + 1, val)
    bst[idx] = val
    val = val + 1
    if idx*2 + 2 < len(bst):
        val = fill_inorder_recursive_bst_array(bst, idx*2 + 2, val)
    return val


def create_balanced_bst_array(size):
    """Creates and returns an array representing a Complete
    (and fully balanced) Binary Tree with "size" elements.
    It's expected that "size" is an integral power of 2 for
    this demo.
    """
    bst = [0] * (size * 2 - 1)
    fill_inorder_recursive_bst_array(bst, 0, 1)
    return bst


def inorder_impl(bst, idx):
    """Iterative inorder traversal implementation.

    Invariant: idx is the index of the current node to visit. This
    method returns the index of the next node to visit. -1 is
    returned if there are no more nodes to visit in the inorder
    traversal.

    The first invocation should pass in the index of the left-most
    node in the tree (i.e. the index of the node with the smallest
    value in the node).

    Runtime Cost to traverse entire BSE: O(n)
    Additional space required per iteration: O(1)
    """
    print("Node Value: ", bst[idx])
    if idx * 2 + 2 < len(bst):
        # Has a right child. Move right and then keep going left.
        idx = idx * 2 + 2
        while idx * 2 + 1 < len(bst):
            idx = idx * 2 + 1
    elif (idx % 2) == 1:
        # Odd index => left child
        # Move to parent (successor)
        idx = int(idx / 2)
    else:
        # Even index => right child
        # Keep moving up till node is right child of parent. As soon as node is left child of parent, stop.
        while (idx % 2) == 0 and idx > 0:
            idx = int((idx - 2) / 2)
        # Now, node is either root or a left child of its parent
        if idx == 0:
            # Root.
            return -1
        else:
            # Left Child of its parent
            idx = int(idx / 2)

    return idx


def inorder(bst):
    idx = int(len(bst) / 2)
    while idx != -1:
        idx = inorder_impl(bst, idx)


def main():
    bst = create_balanced_bst_array(8)
    print("Index:", ", ".join(map(lambda x: "%02i" % x[0], enumerate(bst))))
    print("Value:", ", ".join(map(lambda x: "%02i" % x, bst)))
    print("")
    inorder(bst)


if __name__ == "__main__":
    main()

Output

('Index:', '00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14')
('Value:', '08, 04, 12, 02, 06, 10, 14, 01, 03, 05, 07, 09, 11, 13, 15')

('Node Value: ', 1)
('Node Value: ', 2)
('Node Value: ', 3)
('Node Value: ', 4)
('Node Value: ', 5)
('Node Value: ', 6)
('Node Value: ', 7)
('Node Value: ', 8)
('Node Value: ', 9)
('Node Value: ', 10)
('Node Value: ', 11)
('Node Value: ', 12)
('Node Value: ', 13)
('Node Value: ', 14)
('Node Value: ', 15)