Wednesday, August 05, 2015

print levels of binary tree bottom up

(n):
    if n == null:
        throw
    levels = (n)
    print(levels)

// array of queues
(n):
    levels = new queue[depth(n)]
    (n, levels, depth: 0)
    return levels

(n, levels, depth):
    if n == null:
        return
    level = levels[depth]
    if level == null:
        level = new queue()
        levels[depth] = level
    level.enqueue(n)
    (n.left, levels, depth +1)
    (n.right, levels, depth +1)

depth(n):
    if n == null:
        return 0
    return 1 + max(depth(n.left), depth(n.right))
    
print(levels):
    for i = levels.count() -1, i >= 0, i--:
        level = levels[i]
        for n in level:
            print(n)
        printline()
Using list of queues is better instead of array of queues as the tree is traversed only once.
// list of queues
(n):
    levels = new list()
    (n, levels, depth: 0)
    print(levels)

(n, levels, depth):
    if n == null:
        return
    if levels.count() == depth:
        levels.add(new queue())
    level = levels[depth]
    level.enqueue(n)
    (n.left, levels, depth +1)
    (n.right, levels, depth +1)

No comments:

Post a Comment