"""
Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
"""
from implementations.tree import BinaryTreeNode


def max_depth(tree):
    if not tree:
        return 0
    stack = [(1, tree)]
    max_h = 1
    while stack:
        depth, node = stack.pop()
        if node.left:
            stack.append((depth + 1, node.left))
        if node.right:
            stack.append((depth + 1, node.right))
        if depth > max_h:
            max_h = depth

    return max_h


if __name__ == '__main__':
    t = BinaryTreeNode(5)
    t.left = BinaryTreeNode(2)
    t.right = BinaryTreeNode(3)
    t.left.left = BinaryTreeNode(9)
    t.left.left.left = BinaryTreeNode(12)
    t.right.left = BinaryTreeNode(-1)
    t.right.right = BinaryTreeNode(10)
    print max_depth(t)
