# Title: Binary tree traversals
# Heading: Python Program for Inorder, Preorder and Postorder Traversal
# Level: intermediate
# Tags: tree traversal, inorder, preorder, postorder, binary tree
# Time: O(n)
# Space: O(n)
# About: Visits every node of a small binary tree in in-order, pre-order and post-order with three short recursive functions.

class Node:
    """A value with a left and a right child."""

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


def in_order(node, values):
    """Left subtree, then the node, then the right."""
    if node:
        in_order(node.left, values)
        values.append(node.value)
        in_order(node.right, values)
    return values


def pre_order(node, values):
    """The node, then its left subtree, then its right."""
    if node:
        values.append(node.value)
        pre_order(node.left, values)
        pre_order(node.right, values)
    return values


def post_order(node, values):
    """Left subtree, then the right, then the node."""
    if node:
        post_order(node.left, values)
        post_order(node.right, values)
        values.append(node.value)
    return values


#     1
#    / \
#   2   3
#  / \
# 4   5
root = Node(1, Node(2, Node(4), Node(5)), Node(3))
print("In-order:", in_order(root, []))
print("Pre-order:", pre_order(root, []))
print("Post-order:", post_order(root, []))