link node to its right / left neighbor for every node in binary tree

bfs:

node:
    left, right
    next

(node):
    if node == null:
        throw
    q = new
    level = 0
    q.enqueue({node, level})
    while !q.empty():
        prevn = null
        while !q.isempty() && q.peek().level == level:
            n, nlevel = q.dequeue()
            // link to right
            if prevn != null:
                prevn.next = n
            prevn = n
            // link to left
            n.next = prevn
            prevn = n
            if n.left != null:
                q.enqueue({n.left, nlevel+1})
            if n.right != null:
                q.enqueue({n.right, nlevel+1})
        level++

dfs:

(n, depth = 0, prevs = new list()):
    if n == null:
        return
    if prevs.count() == depth:
        prevs.add(n)
    else:
        prev = prevs[depth]
        prev.next = n
        prevs[depth] = n
    (n.left, depth+1, prevs)
    (n.right, depth+1, prevs)

[Hat tip to PC]