Wednesday, August 05, 2015

print levels of binary tree top down

BFS.

Using level number or with a bool flag that toggles on level change.
(node):
    if node == null:
        throw
    q = new
    currlevel = 1
    q.push(tuple(node, currlevel))
    while !q.isempty():
        n, level = q.pop()
        if level > currlevel:
            printline()
            currlevel = level
        print(n + ", ")
        if n.left != null:
            q.push(tuple(n.left, level +1))
        if n.right != null:
            q.push(tuple(n.right, level +1))
(node):
    if node == null:
        throw
    q = new
    isodd = true // level 1
    q.push(tuple(node, islevelodd: isodd))
    while !q.isempty():
        n, islevelodd = q.pop()
        if islevelodd != isodd:
            printline()
            isodd = islevelodd
        print(n + ", ")
        if n.left != null:
            q.push(tuple(n.left, !islevelodd))
        if n.right != null:
            q.push(tuple(n.right, !islevelodd))
Handling each level at a time.
(node):
    if node == null:
        throw
    q = new
    level = 1
    q.enqueue({node, level})
    while !q.isempty():
        while !q.isempty() && q.peek().level == level:
            n, level = q.dequeue()
            print(n + ", ")
            if n.left != null:
                q.push({n.left, level+1})
            if n.right != null:
                q.push({n.right, level+1})
        print(newline)
        level++
Using dummy node to mark end of level.
(node):
    if node == null:
        throw
    // node marks end of level
    marker = new node()
    q = new
    q.push(node)
    q.push(marker)
    while true:
        n = q.pop()
        if n == marker:
            if q.isEmpty():
                break
            printline()
            q.push(marker)
            continue
        print(n + ", ")
        if n.left != null:
            q.push(n.left)
        if n.right != null:
            q.push(n.right)

No comments:

Post a Comment