CODEWITHSUNDEEP
c++algorithmdata-structurestree
Hemant Bhargava
Hemant Bhargava

Reputation: 3585

connect nodes at same level of an binary tree

I have seen some articles/pages on how to connect the nodes of an binary tree which are at same level but none of those articles explain the process/algorithm clearly. I would appreciate if someone can take this up. Code is not necessary, but explaining it with pseudo will be nice.

For the sake of discussion, let us consider tree as:

               0
           1        2
        3     4   5    6
    7                      9

In above case:

0 should point to null.
1 should point to 2.
3 should point to 4.
....
7 should point to 9.
9 should point to NULL.

Basic tree structure is:

class Tree {
  public:
    int data;
    Tree* left;
    Tree* right;
    Tree* next;
}

Upvotes: 0

Views: 608

Answers (3)

Gribouillis
Gribouillis

Reputation: 2220

Following Ishamael's idea, I'd suggest a procedure along the lines of

void link_levels(Tree* t){
    Tree *head, *tail, *end_of_row;
    assert (t != 0);
    t->next = 0;
    head = tail = end_of_row = t;
    while(head != 0){
        if(head->left != 0){
            tail->next = head->left;
            tail = tail->next;
            tail->next = 0;
        }
        if(head->right != 0){
            tail->next = head->right;
            tail = tail->next;
            tail->next = 0;
        }
        if(head == end_of_row){
            head = head->next;
            end_of_row->next = 0;
            end_of_row = tail;
        }
        else {
            head = head->next;
        }
    }
}

Upvotes: 1

Ishamael
Ishamael

Reputation: 12795

There's an interesting approach that doesn't use extra memory, which is sort of inductive:

  1. The first level is already connected (it only has one node)

  2. Let's say level i is connected. Then to connect level i+1 do the following:

    a) Initialize node lst (just an intermediate variable we will use later) to null

    b) Start at the first node on level i.

    c) Traverse nodes on level i starting from the first node. Note that you can easily traverse nodes on level i because it is already connected, so you have sibling pointers in each node.

    d) For each node on level i look first at its left child, then at its right child. For each child that is not null, if lst is not null, connect lst to that child. Then set lst to that child.

Once you connected level i + 1, you can move on to the next level. If after traversing the level lst is still null, it means that no node on this level had a child => this was the last level, you can stop the algorithm.

It is easy to show why this works, it takes linear time and constant space, so it is strictly better than BFS with a queue (which takes linear memory).

Upvotes: 1

Amit Kumar
Amit Kumar

Reputation: 1517

Use BFS as suggested in the comments. Then you will have each node's distance from the root.

pseudo code:

 vis[1..n] = false   // mark each node as un-visited
 dis[1..n] = 0
 Queue q
 dis[root] = 0 
 vis[root] = true
 q.push(root)
 while !q.empty()
     node x = q.front()
     children[] = children nodes of node x
     for each child in children 
          !vis[child] 
            dis[child] = dis[x] + 1 
            vis[child] =true 
            q.enqueue(child)
     q.pop()

Now you will have each nodes distance from root, aggregate each node based on the distance , and can join the nodes as per your requirements.

Upvotes: 0

Related Questions