"""Incomplete Binary Search Tree implementation.
Author: Francois Pitt, March 2013,
        Danny Heap, October 2013.
"""

class BST:
    """A Binary Search Tree."""

    def __init__(self: 'BST', container: list =None) -> None:
        """
        Initialize this BST by inserting the items from container (default [])
        one by one, in the order given.
        """
        # Initialize empty tree.
        self.root = None
        # Insert every item from container.
        if container:
            for item in container:
                self.insert(item)

    def __str__(self: 'BST'):
        """
        Return a "sideways" representation of the items in this BST, with
        right subtrees above nodes above left subtrees and each item preceded
        by a number of TAB characters equal to its depth.
        """
        # Tricky to do iteratively so we cheat,
        # You could take up the challenge...
        return BST._str("", self.root)
# a possible stack-based version
#def __str__(self):
#
#        notprinted = []
#        string = ""
#        s = Stack()
#        s.push(self.root)
#        while not s.is_empty():
#            n = s.pop()
#            if n.left:
#                s.push(n.left)
#            if n.right:
#                s.push(n.right)
#            notprinted.append(n)
#        s.push((self.root, ""))
#        while not s.is_empty():
#            n = s.pop()
#            if n[0].right and n[0].right in notprinted:
#                s.push(n)
#                s.push((n[0].right, n[1] + "\t"))
#            else:
#                string += n[1] + str(n[0].value) + "\n"
#                notprinted.remove(n[0])
#                if n[0].left:
#                    s.push((n[0].left, n[1] + "\t"))
#        return string

    # Recursive helper for __str__.
    def _str(indent: str, root: '_BSTNode') -> str:
        """
        Return a "sideways" representation of the items in the BST rooted at
        root, with right subtrees above nodes above left subtrees and each
        item preceded by a number of TAB characters equal to its depth, plus
        indent.
        """
        if root:
            return (BST._str(indent + "\t", root.right) +
                    indent + str(root.item) + "\n" +
                    BST._str(indent + "\t", root.left))
        else:
            return ""

    def insert(self: 'BST', item: object) -> None:
        """
        Insert item into this BST.
        """
        # Find the point of insertion.
        parent, current = None, self.root
        while current:
            if item < current.item:
                parent, current = current, current.left
            else:  # item > current.item
                parent, current = current, current.right
        # Create a new node and link it in appropriately.
        new_node = _BSTNode(item)
        if parent:
            if item < parent.item:
                parent.left = new_node
            else:  # item > parent.item
                parent.right = new_node
        else:
            self.root = new_node

    def count_less(self: 'BST', item: object) -> int:
        """
        Return the number of nodes in this BST with items that are 
        less than given item.
        """
        stack = Stack()
        count = 0
        stack.push(self.root)
        while not stack.is_empty():
            node = stack.pop()
            if node: # only count non-empty nodes
                if node.item < item:
                    count += 1
                    stack.push(node.right)
                stack.push(node.left)
        return count


    def size(self: 'BST') -> int:
        """Return number of nodes in BST self"""
        stack = Stack()
        count = 0
        stack.push(self.root)
        while not stack.is_empty():
            node = stack.pop()
            if node: # only count non-empty nodes
                count += 1
                stack.push(node.left)
                stack.push(node.right)
        return count


class _BSTNode:
    """A node in a BST."""

    def __init__(self: '_BSTNode', item: object, 
                 left: '_BSTNode' =None, right: '_BSTNode' =None) -> None:
        """
        Initialize this node to store item and have children left and right.
        """
        self.item, self.left, self.right = item, left, right



'''Stack ADT.

Operations:
	pop: remove and return top item
        push(item): store item on top of stack
        is_empty: return whether stack is empty.
'''

class Stack:

    '''A last-in, first-out (LIFO) stack of items'''

    def __init__(self):
        '''A new empty Stack.'''

        self._data = []
        
    def pop(self):
        '''Remove and return the top item.'''

        return self._data.pop()
        
    def is_empty(self):
        '''Return whether the stack is empty.'''

        return self._data == []
    
    def push(self, o):
        '''Place o on top of the stack.'''

        self._data.append(o)