class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def height(r):
    height = 0
    s = r
    while s:
        height += 1
        s = s.left
    return height

def printVS(r, level):
    if not r: return
    if 1 == level:
        print r.key
    elif level >= 1:
        printVS(r.left, level-1)
        printVS(r.right, level-1)

def rbfs(r):
    for i in range(1, height(r)+1):
        printVS(r, i)

def bfs(r):
    q = []
    q.append(r)
    while len(q) > 0:
        node = q.pop()
        print node.key
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

if __name__ == "__main__":
    r = Node(5)
    n1 = Node(57)
    n2 = Node(13)
    n3 = Node(313)
    n4 = Node(890)
    n5 = Node(39)
    n6 = Node(1000)
    n7 = Node(225)
    n8 = Node(38)
    n9 = Node(15)
    n10 = Node(333)
    ###
    r.left = n1
    r.right = n2
    n1.left = n3
    n1.right = n4
    n2.left = n5
    n2.right = n6
    n3.left = n7
    n3.right = n8
    n4.left = n9
    n4.right = n10

    #rbfs(r)
    bfs(r)

dbcaa294d4957b31c1392f51a5481598368a7508
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def height(r):
    height = 0
    s = r
    while s:
        height += 1
        s = s.left
    return height

def printVS(r, level):
    if not r: return
    if 1 == level:
        print r.key
    elif level >= 1:
        printVS(r.left, level-1)
        printVS(r.right, level-1)

def rbfs(r):
    for i in range(1, height(r)+1):
        printVS(r, i)

def bfs(r):
    q = []
    q.append(r)
    while len(q) > 0:
        node = q.pop()
        print node.key
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

if __name__ == "__main__":
    r = Node(5)
    n1 = Node(57)
    n2 = Node(13)
    n3 = Node(313)
    n4 = Node(890)
    n5 = Node(39)
    n6 = Node(1000)
    n7 = Node(225)
    n8 = Node(38)
    n9 = Node(15)
    n10 = Node(333)
    ###
    r.left = n1
    r.right = n2
    n1.left = n3
    n1.right = n4
    n2.left = n5
    n2.right = n6
    n3.left = n7
    n3.right = n8
    n4.left = n9
    n4.right = n10

    #rbfs(r)
    bfs(r)
