Binary Tree

class TreeNode:

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

class BinaryTree:

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

    # traversal: recursion
    def preorder(self, root):
        if not root:
            return []
        return [root.val] + self.preorder(root.left) + self.preorder(
            root.right)

    def inorder(self, root):
        if not root:
            return []
        return self.inorder(root.left) + [root.val] + self.inorder(root.right)

    def postorder(self, root):
        if not root:
            return []
        return self.postorder(root.left) + self.postorder(
            root.right) + [root.val]

    # traversal: iteration
    def preorder2(self, root):
        if not root:
            return []

        result, stack = [], [root]
        while stack != []:
            root = stack.pop()
            result.append(root.val)
            if root.right:
                stack.append(root.right)
            if root.left:
                stack.append(root.left)

        return result

    def inorder2(self, root):
        result = []
        stack = []

        while root or stack != []:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            result.append(root.val)
            root = root.right
        return result

    def postorder2(self, root):
        result = []
        stack = [(root, False)]

        while stack:
            root, visited = stack.pop()
            if root:
                if visited:
                    result.append(root.val)
                else:
                    stack.append((root, True))
                    stack.append((root.right, False))
                    stack.append((root.left, False))
        return result

# Set up a Binary Tree
#        1
#       / \
#     2     3
#   /   \  /  \
#  4    5 6    7

bt = BinaryTree(1)
bt.root.left = TreeNode(2)
bt.root.right = TreeNode(3)
bt.root.left.left = TreeNode(4)
bt.root.left.right = TreeNode(5)
bt.root.right = TreeNode(3)
bt.root.right.left = TreeNode(6)
bt.root.right.right = TreeNode(7)

# print Binary Tree
print("Preorder Traversal by recursion:", bt.preorder(bt.root))
print("Preorder Traversal by iteration:", bt.preorder2(bt.root))
print("Inorder Traversal by recursion:", bt.inorder(bt.root))
print("Inorder Traversal by iteration:", bt.inorder2(bt.root))
print("Postorder Traversal by recursion:", bt.postorder(bt.root))
print("Postorder Traversal by iteration:", bt.postorder2(bt.root))