#!/usr/bin/env python3
#
# An implementation of a binary search tree in python where the value of each
# node is an integer.
#
from typing import Optional

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

    def __str__(self):
        return f"({self.value})"

    def __repr__(self):
        return self.__str__()


class BinarySearchTree:
    def __init__(self, root: TreeNode=None):
        self.root = root

    def __repr__(self) -> str:
        """
        >>> bst = BinarySearchTree()
        >>> print(bst)
        <BLANKLINE>

        >>> bst = BinarySearchTree(TreeNode(1))
        >>> print(bst)
        (1)

        >>> bst.insert(TreeNode(10))
        >>> print(bst)
        (1)(10)

        >>> bst.insert(TreeNode(2))
        >>> print(bst)
        (1)(2)(10)

        >>> bst.insert(TreeNode(8))
        >>> print(bst)
        (1)(2)(8)(10)
        """
        return self._repr_helper(self.root, "")

    def _repr_helper(self, current: TreeNode, string: str) -> str:
        """ An internal helper method for :func:`__repr__` """
        if current is None:
            return string

        string = self._repr_helper(current.left, string)
        string += str(current)
        string = self._repr_helper(current.right, string)

        return string

    def depth(self) -> int:
        """
        Returns the maximum depth of a BinarySearchTree.
        >>> bst = BinarySearchTree()
        >>> bst.depth()
        0

        >>> bst = BinarySearchTree(TreeNode(1))
        >>> bst.depth()
        1

        >>> bst.insert(TreeNode(4))
        >>> bst.insert(TreeNode(6))
        >>> bst.depth()
        3
        """
        return self._depth(self.root, 0)

    def _depth(self, current: TreeNode, depth: int) -> int:
        """
        An internal helper method for :func:`depth`.
        """
        if current is None:
            return depth

        # Pre-order traversal (depth-first search)
        left_depth = self._depth(current.left, depth)
        depth += 1
        right_depth = self._depth(current.right, depth)

        return max(left_depth, right_depth)

    def insert(self, node: TreeNode):
        """
        Inserts the given *node* into a valid position in the BinarySearchTree.

        >>> bst = BinarySearchTree(TreeNode(3))
        >>> print(bst)
        (3)

        >>> bst = BinarySearchTree()
        >>> bst.insert(TreeNode(1))
        >>> bst.insert(TreeNode(4))
        >>> bst.insert(TreeNode(3))
        >>> bst.insert(TreeNode(5))
        >>> print(bst)
        (1)(3)(4)(5)
        """
        if self.root is None:
            self.root = node
            return

        self._insert_recursive(self.root, node)

    def _insert_recursive(self, current: TreeNode, node: TreeNode) -> TreeNode:
        """ An internal helper method for :func:`insert`. """
        if current is None:
            return node

        if node.value < current.value:
            current.left = self._insert_recursive(current.left, node)
        elif node.value > current.value:
            current.right = self._insert_recursive(current.right, node)

        return current

    def search(self, value: int) -> Optional[TreeNode]:
        """
        Returns the node matching the given key *value* if it exists in the
        BinarySearchTree. Otherwise, returns None.

        >>> bst = BinarySearchTree(TreeNode(3))
        >>> bst.search(3)
        (3)

        >>> bst.search(9)

        >>> bst.insert(TreeNode(4))
        >>> bst.insert(TreeNode(1))
        >>> bst.insert(TreeNode(-4))
        >>> bst.search(1)
        (1)
        """
        return self._search_recursive(self.root, value)

    def _search_recursive(self, current: TreeNode, value: int) -> Optional[TreeNode]:
        """
        An internal helper method for :func:`search`. Performs a depth-first
        search for the given *value*.
        """
        if current is None:
            return None

        if current.value == value:
            return current

        else:
            return self._search_recursive(current.left, value) or \
                self._search_recursive(current.right, value)


if __name__ == "__main__":
    import doctest
    doctest.testmod()
