Link Tree nodes at each level

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 effi开发者_运维技巧cient algorithm.

Thanks

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);
    }

Create a vector of linked lists. Do a DFS keeping track of your level, and for each node you find, add it to the linked list of the level. This will run in O(n) which is optimal.

Is this what you want to do?

This is not a direct answer to the question and may not be applicable based on your situation. But if you have control over the creation and maintenance of the binary tree, it would probably be more efficient to maintain the links while building/updating the tree.

If you kept both left and right pointers at each level, then it would be "simple" (always easy to say that word when someone else is doing the work) to maintain them. When inserting a new node at a given level, you know its direct siblings from the parent node information. You can adjust the left and right pointers for the three nodes involved (assuming not at the edge of the tree). Likewise, when removing a node, simply update the left and right pointers of the siblings of the node being removed. Change them to point to each other.

I agree with Thomas Ahle's answer if you want to make all of the row-lists at the same time. It seems that you are only interested in making the list for a one specific row.

Let's say you have a giant tree, but you only want to link the 5th row. There's clearly no point in accessing any node below the 5th row. So just do an early-terminated DFS. Unfortunately, you still have to run through all of the ancestors of every node in the list.

But here's the good news. If you have a perfect binary tree (where every single node branches exactly twice except for the last row) then the first row will have 1 one, the second 2, the third 4, the fourth 8 and the fifth 16. Thus there are more nodes on the last row (16) than all the previous put together (1 + 2 + 4 + 8 = 15), so searching through all of the ancestors is still just O(n), where n is the number of nodes in the row.

The worst case on the other hand would be to have the fifth row consist of a single node with a full binary tree above it. Then you still have to search through all 15 ancestors just to put that one node on the list.

So while this algorithm is really your only choice without modifying your data structure its efficiency relies entirely on how populated the row is compared to higher rows.

#include <queue>

struct Node {
    Node *left;
    Node *right;
    Node *next;
};

/** Link all nodes of the same level in a binary tree. */
void link_level_nodes(Node *pRoot)
{
    queue<Node*> q;
    Node *prev;     // Pointer to the revious node of the current level
    Node *node;
    int cnt;        // Count of the nodes in the current level
    int cntnext;    // Count of the nodes in the next level

    if(NULL == pRoot)
        return;

    q.push(pRoot);
    cnt = 1;
    cntnext = 0;
    prev = NULL;

    while (!q.empty()) {
        node = q.front();
        q.pop();

        /* Add the left and the right nodes of the current node to the queue
           and increment the counter of nodes at the next level. 
        */
        if (node->left){
            q.push(node->left);
            cntnext++;
        }
        if (node->right){
            q.push(node->right);
            cntnext++;
        }

        /* Link the previous node of the current level to this node */
        if (prev)
            prev->next = node;

        /* Se the previous node to the current */
        prev = node;

        cnt--;
        if (0 == cnt) { // if this is the last node of the current level
            cnt = cntnext;
            cntnext = 0;
            prev = NULL;
        }
    }
}

What I usually do to solve this problem is that I do a simple inorder traversal.

I initialize my tree with a constructor that gives a level or column value to every node. Hence my head is at Level 0.

public Node(int d)
{
head=this;
data=d;
left=null;
right=null;
level=0;
}

Now, if in the traversal, I take a left or a right, I simply do the traversal with a level indicator. For each level identifier, I make a Linked List, possibly in a Vector of Nodes.

Different approaches can be used to solve this problem. Some of them that comes to mind are -

1) Using level order traversal or BFS.
We can modify queue entries to contain level of nodes.So queue node will contain a pointer to a tree node and an integer level. When we deque a node we can check the level of dequeued node if it is same we can set right pointer to point to it.
Time complexity for this method would be O(n).

2) If we have complete binary tree we can extend Pre-Order traversal. In this method we shall set right pointer of parent before the children.
Time complexity for this method would be O(n).

3) In case of incomplete binary tree we can modify method (2) by traversing first root then right pointer and then left so we can make sure that all nodes at level i have the right pointer set, before the level i+1 nodes. Time complexity for this method would be O(n^2).

    private class Node
    {
        public readonly Node Left;
        public readonly Node Right;
        public Node Link { get; private set; }

        public void Run()
        {
            LinkNext = null;
        }

        private Node LinkNext
        {
            get
            {
                return Link == null ? null : (Link.Left ?? Link.Right ?? Link.LinkNext);
            }
            set
            {
                Link = value;
                if (Right != null)
                    Right.LinkNext = LinkNext;
                if (Left != null)
                    Left.LinkNext = Right ?? LinkNext;
            }
        }
    }

Keep a depth array while breadth-first search.

    vector<forward_list<index_t>> level_link(MAX_NODES);
    index_t fringe_depth = 0;
    static index_t depth[MAX_NODES];
    memset(depth,0,sizeof(depth));
    depth[0] = 0;

Now when the depth-changes while de-queuing, you get all linked !

    explored[0] = true;
    static deque<index_t> fringe;
    fringe.clear();
    fringe.push_back(0); // start bfs from node 0
    while(!fringe.empty()) {
        index_t xindex = fringe.front();
        fringe.pop_front();
        if(fringe_depth < depth[xindex]) {
            // play with prev-level-data
            fringe_depth = depth[xindex];
        }

Now we have fringe-depth, so we can level-link.

        level_link[fringe_depth].push_front(xindex);

        for(auto yindex : nodes[xindex].connected) {
            if(explored[yindex])
                continue;
            explored[yindex] = true;
            depth[yindex] = depth[xindex] + 1;
            fringe.push_back(yindex);
        }
    }