connect nodes at same level of an binary tree

Question

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

You can Traverse the tree levelwise using Breadth-first search Algorithm and on every level you can temporaryily store a previous node. Then the next of previous node will be currently parsed node. — sameerkn
– sameerkn, Commented Jan 17, 2017 at 7:07
Yes, use bfs or breadth first search which traverses in layers , so basically you will have nodes at the same level at the same distance from the root. — Amit Kumar
– Amit Kumar, Commented Jan 17, 2017 at 7:13
@sameerkn, I understand that. Would you mind writing pseudo code please? — Hemant Bhargava
– Hemant Bhargava, Commented Jan 17, 2017 at 7:15

Ishamael · Accepted Answer · 2017-01-17 07:41:53Z

1

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

The first level is already connected (it only has one node)
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).

answered Jan 17, 2017 at 7:41

Ishamael

12.8k4 gold badges38 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Gribouillis Over a year ago

A variant on this is to simply use the node themselves as the queue items by using their next pointer. We only need to keep a pointer to the next end of row because when the end of the current row is processed, the tail of the queue points to the end of the next row.

Gribouillis · Accepted Answer · 2017-01-17 08:35:27Z

1

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

answered Jan 17, 2017 at 8:35

Gribouillis

2,2501 gold badge11 silver badges16 bronze badges

Comments

Amit Kumar · Accepted Answer · 2017-01-17 07:26:49Z

0

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.

answered Jan 17, 2017 at 7:26

Amit Kumar

1,5371 gold badge17 silver badges28 bronze badges

1 Comment

Gribouillis Over a year ago

The nodes can be linked together in the same loop because they'll appear in the queue in the order 0 1 2 3 4 5 6 7 9.

Collectives™ on Stack Overflow

connect nodes at same level of an binary tree

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related