# -*- Python -*-

import sys

# different tree traversals
# depth-first: inorder, preorder, postorder

# tree representation:
# [<data>, <child>, <child>]

W = sys.stdout.write

t = [4, [2, [1, None, None], [3, None, None]], [6, [5, None, None], [7, None, None]]]

def make_tree (depth, counter):
    "make a complete binary tree"
    if depth == 0:
        value, counter[0] = counter[0], counter[0] + 1
        return (value, None, None)
    else:
        l = make_tree (depth - 1, counter)
        value, counter[0] = counter[0], counter[0] + 1
        r = make_tree (depth - 1, counter)
        return value, l, r

t = make_tree (3, [1])

# 4261357

def breadth_first (t):
    todo = [t]
    while todo:
        top = todo.pop (0)
        W ('%s ' % top[0])
        if top[1]:
            todo.append (top[1])
        if top[2]:
            todo.append (top[2])        

def depth_preorder (t):
    if t:
        [n, l, r] = t
        W ('%s ' % n)
        depth_preorder (l)
        depth_preorder (r)    

def depth_inorder (t):
    if t:
        [n, l, r] = t
        depth_inorder (l)
        W ('%s ' % n)
        depth_inorder (r)    

def depth_postorder (t):
    if t:
        [n, l, r] = t
        depth_postorder (l)
        depth_postorder (r)    
        W ('%s ' % n)

if __name__ == '__main__':
    W ('breadth\n')
    breadth_first (t)
    W ('\npreorder\n')
    depth_preorder (t)
    W ('\ninorder\n')
    depth_inorder (t)
    W ('\npostorder\n')
    depth_postorder (t)
    W ('\n')