Link Tree nodes at each level

Question

Given a binary tree, how would you join the nodes at each level, left to right. Say there are 5 nodes at level three, link all of them from left to right.

I don't need anybody to write code for this.. but just an efficient algorithm.

Thanks

Answer 1

Idea is:
1. Traverse tree with BFS.
2. When you do traversing, you're linking nodes on next level - if node has left and right node, you'll link left to right. If node has next node, then you link rightmost child of current node to leftmost child of next node.

    public void BreadthFirstSearch(Action<Node> currentNodeAction)
    {
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);

        while (q.Count != 0)
        {
            Node current = q.Dequeue();

            if (currentNodeAction != null)
                currentNodeAction(current);

            if (current.left != null) q.Enqueue(current.left);
            if (current.right != null) q.Enqueue(current.right);
        }
    }

    private void Linker(Node node)
    {
        Link(node.left, node.right);

        if (node.next != null)
            Link(node.right ?? node.left, node.next.left ?? node.next.right);
    }

    private void Link(Node node1, Node node2)
    {
        if (node1 != null && node2 != null)
            node1.next = node2;
    }

    public void LinkSameLevel()
    {
        BreadthFirstSearch(Linker);
    }