Sunday, July 19, 2015

print binary tree nodes in vertical zigzag order

//example
          5
        /   \
       3     7
      / \   / \
     1   4 6   8
        /   \   \
       2     9   10

prints:
1
2 3
5 4 6
9 7
8
10
vertical-zigzag(n):
    if n == null:
        throw
    leftwidth, rightwidth = widths(n, 0)
    size = rightwidth - leftwidth +1
    a = init(size)
    bfs(n, a, index: -leftwidth)
    print(a)

bfs(node, a, index):
    q = new
    q.enqueue(tuple(node, index))
    while !q.empty():
        n, i = q.dequeue()
        if i &1 == 0: // even
            ((queue)a[i]).enqueue(n.value)
        else: // odd
            ((stack)a[i]).push(n.value)
        if n.left != null:
            q.enqueue(tuple(n.left, i-1))
        if n.left != null:
            q.enqueue(tuple(n.right, i+1))

widths(n, offset):
    if n == null:
        throw
    leftwidth = min(offset, 0)  // min so leftwidth is not +ve
    rightwidth = max(offset, 0) // max so rightwidth is not -ve
    if n.left != null:
        childleftwidth, childrightwidth = widths(n.left, offset -1)
        leftwidth = min(leftwidth, childleftwidth)
        rightwidth = max(rightwidth, childrightwidth)
    if n.right != null:
        childleftwidth, childrightwidth = widths(n.right, offset +1)
        leftwidth = min(leftwidth, childleftwidth)
        rightwidth = max(rightwidth, childrightwidth)
    return leftwidth, rightwidth

// simpler
widths(n, offset):
    if n == null:
        return 0, 0
    leftlw, leftrw = (n.left, offset -1)
    rightlw, rightrw = (n.right, offset +1)
    leftwidth = min(leftlw, rightlw, offset)  // min left widths, offset
    rightwidth = max(leftrw, rightrw, offset) // max right widths, offset
    return leftwidth, rightwidth

init(size):
    a = new [size]
    for i = 0, i < a.length, i++:
        // even: queue, odd: stack
        if i &1 == 0: // even
            a[i] = new queue()
        else: // odd
            a[i] = new stack()
    return a

print(a):
    for i = 0, i < a.length, i++:
        if i &1 == 0: // even
            q = (queue)a[i]
            while !q.empty():
                print(q.dequeue())
        else: // odd
            s = (stack)a[i]
            while !s.empty():
                print(s.pop())
        printline()
Code is cleaner with these 2 common methods as only init() is aware of newed objects.
add(stack, x):
    stack.push(x)
x remove(stack):
    return stack.pop()

add(queue, x):
    queue.enqueue(x)
x remove(queue):
    return queue.dequeue()

No comments:

Post a Comment