# Connect nodes at same level

Write a function to connect all the adjacent nodes at the same level in a binary tree. Structure of the given Binary Tree node is like following.

 struct node{   int data;   struct node* left;   struct node* right;   struct node* nextRight;   }

Initially, all the nextRight pointers point to garbage values. Your function should set these pointers to point next right for each node.

Example:

Input Tree
A
/
B   C
/
D   E   F

Output Tree
A--->NULL
/
B-->C-->NULL
/
D-->E-->F-->NULL

Method 1 (Extend Level Order Traversal or BFS)
Consider the method 2 of Level Order Traversal. The method 2 can easily be extended to connect nodes of same level. We can augment queue entries to contain level of nodes also which is 0 for root, 1 for root’s children and so on. So a queue node will now contain a pointer to a tree node and an integer level. When we enqueue a node, we make sure that correct level value for node is being set in queue. To set nextRight, for every node N, we dequeue the next node from queue, if the level number of next node is same, we set the nextRight of N as address of the dequeued node, otherwise we set nextRight of N as NULL.

Please refer connect Nodes at same Level (Level Order Traversal) for implementation.

Time Complexity: O(n)

Method 2 (Extend Pre Order Traversal)
This approach works only for Complete Binary Trees. In this method we set nextRight in Pre Order fashion to make sure that the nextRight of parent is set before its children. When we are at node p, we set the nextRight of its left and right children. Since the tree is complete tree, nextRight of p’s left child (p->left->nextRight) will always be p’s right child, and nextRight of p’s right child (p->right->nextRight) will always be left child of p’s nextRight (if p is not the rightmost node at its level). If p is the rightmost node, then nextRight of p’s right child will be NULL.

## C++

 // CPP program to connect nodes // at same level using extended  // pre-order traversal  #include  #include using namespace std;     class node  {      public:     int data;      node* left;      node* right;      node *nextRight;             /* Constructor that allocates a new node with the      given data and NULL left and right pointers. */     node(int data)     {         this->data = data;         this->left = NULL;         this->right = NULL;         this->nextRight = NULL;     } };     void connectRecur(node* p);     // Sets the nextRight of  // root and calls connectRecur()  // for other nodes  void connect(node *p)  {      // Set the nextRight for root      p->nextRight = NULL;         // Set the next right for rest of the nodes      // (other than root)      connectRecur(p);  }     /* Set next right of all descendents of p.  Assumption: p is a compete binary tree */ void connectRecur(node* p)  {      // Base case      if (!p)          return;             // Set the nextRight pointer for p's left child      if (p->left)          p->left->nextRight = p->right;             // Set the nextRight pointer     // for p's right child p->nextRight     // will be NULL if p is the right      // most child at its level      if (p->right)          p->right->nextRight = (p->nextRight)? p->nextRight->left: NULL;             // Set nextRight for other     // nodes in pre order fashion      connectRecur(p->left);      connectRecur(p->right);  }           /* Driver code*/ int main()  {         /* Constructed binary tree is                  10              /               8 2          /          3      */     node *root = new node(10);      root->left = new node(8);      root->right = new node(2);      root->left->left = new node(3);             // Populates nextRight pointer in all nodes      connect(root);             // Let us check the values     // of nextRight pointers      cout<<"Following are populated nextRight pointers in the tree"         " (-1 is printed if there is no nextRight) ";      cout<<"nextRight of "<data<< " is "         << (root->nextRight? root->nextRight->data: -1) <left->data<< " is "         << (root->left->nextRight? root->left->nextRight->data: -1) <right->data<< " is "         << (root->right->nextRight? root->right->nextRight->data: -1) <left->left->data<< " is "         << (root->left->left->nextRight? root->left->left->nextRight->data: -1) <

## C

 // C program to connect nodes at same level using extended // pre-order traversal #include #include    struct node {   int data;   struct node *left;   struct node *right;   struct node *nextRight; };    void connectRecur(struct node* p);    // Sets the nextRight of root and calls connectRecur()  // for other nodes void connect (struct node *p) {     // Set the nextRight for root     p->nextRight = NULL;        // Set the next right for rest of the nodes      // (other than root)     connectRecur(p); }    /* Set next right of all descendents of p.    Assumption:  p is a compete binary tree */ void connectRecur(struct node* p) {   // Base case   if (!p)     return;      // Set the nextRight pointer for p's left child   if (p->left)     p->left->nextRight = p->right;      // Set the nextRight pointer for p's right child   // p->nextRight will be NULL if p is the right    // most child at its level   if (p->right)     p->right->nextRight = (p->nextRight)? p->nextRight->left: NULL;      // Set nextRight for other nodes in pre order fashion   connectRecur(p->left);   connectRecur(p->right); }    /* UTILITY FUNCTIONS */ /* Helper function that allocates a new node with the    given data and NULL left and right pointers. */ struct node* newnode(int data) {   struct node* node = (struct node*)                        malloc(sizeof(struct node));   node->data = data;   node->left = NULL;   node->right = NULL;   node->nextRight = NULL;      return(node); }    /* Driver program to test above functions*/ int main() {      /* Constructed binary tree is             10           /           8      2       /     3   */   struct node *root = newnode(10);   root->left        = newnode(8);   root->right       = newnode(2);   root->left->left  = newnode(3);      // Populates nextRight pointer in all nodes   connect(root);      // Let us check the values of nextRight pointers   printf("Following are populated nextRight pointers in the tree "     "(-1 is printed if there is no nextRight) ");   printf("nextRight of %d is %d ", root->data,    root->nextRight? root->nextRight->data: -1);   printf("nextRight of %d is %d ", root->left->data,    root->left->nextRight? root->left->nextRight->data: -1);   printf("nextRight of %d is %d ", root->right->data,    root->right->nextRight? root->right->nextRight->data: -1);   printf("nextRight of %d is %d ", root->left->left->data,    root->left->left->nextRight? root->left->left->nextRight->data: -1);   return 0; }

## Java

 // Java program to connect nodes at same level using extended // pre-order traversal     // A binary tree node class Node  {     int data;     Node left, right, nextRight;         Node(int item)      {         data = item;         left = right = nextRight = null;     } }     class BinaryTree  {     Node root;         // Sets the nextRight of root and calls connectRecur()     // for other nodes     void connect(Node p)      {             // Set the nextRight for root         p.nextRight = null;             // Set the next right for rest of the nodes (other         // than root)         connectRecur(p);     }         /* Set next right of all descendents of p.        Assumption:  p is a compete binary tree */     void connectRecur(Node p)      {         // Base case         if (p == null)             return;             // Set the nextRight pointer for p's left child         if (p.left != null)             p.left.nextRight = p.right;             // Set the nextRight pointer for p's right child         // p->nextRight will be NULL if p is the right most child          // at its level         if (p.right != null)              p.right.nextRight = (p.nextRight != null) ?                                           p.nextRight.left : null;             // Set nextRight for other nodes in pre order fashion         connectRecur(p.left);         connectRecur(p.right);     }         // Driver program to test above functions      public static void main(String args[])      {         BinaryTree tree = new BinaryTree();                    /* Constructed binary tree is              10             /            8     2          /         3         */         tree.root = new Node(10);         tree.root.left = new Node(8);         tree.root.right = new Node(2);         tree.root.left.left = new Node(3);             // Populates nextRight pointer in all nodes         tree.connect(tree.root);             // Let us check the values of nextRight pointers         System.out.println("Following are populated nextRight pointers in "                 + "the tree" + "(-1 is printed if there is no nextRight)");         int a = tree.root.nextRight != null ? tree.root.nextRight.data : -1;         System.out.println("nextRight of " + tree.root.data + " is "                 + a);         int b = tree.root.left.nextRight != null ?                                      tree.root.left.nextRight.data : -1;         System.out.println("nextRight of " + tree.root.left.data + " is "                 + b);         int c = tree.root.right.nextRight != null ?                                     tree.root.right.nextRight.data : -1;         System.out.println("nextRight of " + tree.root.right.data + " is "                 + c);         int d = tree.root.left.left.nextRight != null ?                                tree.root.left.left.nextRight.data : -1;         System.out.println("nextRight of " + tree.root.left.left.data + " is "                 + d);      } }     // This code has been contributed by Mayank Jaiswal

## Python3

 # Python3 program to connect nodes at same  # level using extended pre-order traversal     class newnode:     def __init__(self, data):         self.data = data         self.left = self.right = self.nextRight = None            # Sets the nextRight of root and calls  # connectRecur() for other nodes  def connect (p):            # Set the nextRight for root      p.nextRight = None        # Set the next right for rest of     # the nodes (other than root)      connectRecur(p)    # Set next right of all descendents of p.  # Assumption: p is a compete binary tree  def connectRecur(p):            # Base case      if (not p):         return            # Set the nextRight pointer for p's      # left child      if (p.left):          p.left.nextRight = p.right             # Set the nextRight pointer for p's right     # child p.nextRight will be None if p is      # the right most child at its level      if (p.right):         if p.nextRight:             p.right.nextRight = p.nextRight.left         else:             p.right.nextRight = None            # Set nextRight for other nodes in     # pre order fashion      connectRecur(p.left)      connectRecur(p.right)    # Driver Code if __name__ == '__main__':        # Constructed binary tree is      #         10      #     /       #     8     2      # /      # 3      root = newnode(10)      root.left     = newnode(8)      root.right     = newnode(2)      root.left.left = newnode(3)         # Populates nextRight pointer in all nodes      connect(root)         # Let us check the values of nextRight pointers      print("Following are populated nextRight",            "pointers in the tree (-1 is printed",                     "if there is no nextRight)")     print("nextRight of", root.data, "is ", end = "")     if root.nextRight:         print(root.nextRight.data)     else:         print(-1)     print("nextRight of", root.left.data, "is ", end = "")      if root.left.nextRight:         print(root.left.nextRight.data)     else:         print(-1)     print("nextRight of", root.right.data, "is ", end = "")      if root.right.nextRight:         print(root.right.nextRight.data)     else:         print(-1)     print("nextRight of", root.left.left.data, "is ", end = "")      if root.left.left.nextRight:         print(root.left.left.nextRight.data)     else:         print(-1)    # This code is contributed by PranchalK

## C#

 using System;    // C# program to connect nodes at same level using extended  // pre-order traversal     // A binary tree node  public class Node {     public int data;     public Node left, right, nextRight;        public Node(int item)     {         data = item;         left = right = nextRight = null;     } }    public class BinaryTree {     public Node root;        // Sets the nextRight of root and calls connectRecur()      // for other nodes      public virtual void connect(Node p)     {            // Set the nextRight for root          p.nextRight = null;            // Set the next right for rest of the nodes (other          // than root)          connectRecur(p);     }        /* Set next right of all descendents of p.         Assumption:  p is a compete binary tree */     public virtual void connectRecur(Node p)     {         // Base case          if (p == null)         {             return;         }            // Set the nextRight pointer for p's left child          if (p.left != null)         {             p.left.nextRight = p.right;         }            // Set the nextRight pointer for p's right child          // p->nextRight will be NULL if p is the right most child           // at its level          if (p.right != null)         {             p.right.nextRight = (p.nextRight != null) ? p.nextRight.left : null;         }            // Set nextRight for other nodes in pre order fashion          connectRecur(p.left);         connectRecur(p.right);     }        // Driver program to test above functions       public static void Main(string[] args)     {         BinaryTree tree = new BinaryTree();            /* Constructed binary tree is               10              /              8     2           /          3          */         tree.root = new Node(10);         tree.root.left = new Node(8);         tree.root.right = new Node(2);         tree.root.left.left = new Node(3);            // Populates nextRight pointer in all nodes          tree.connect(tree.root);            // Let us check the values of nextRight pointers          Console.WriteLine("Following are populated nextRight pointers in " + "the tree" + "(-1 is printed if there is no nextRight)");         int a = tree.root.nextRight != null ? tree.root.nextRight.data : -1;         Console.WriteLine("nextRight of " + tree.root.data + " is " + a);         int b = tree.root.left.nextRight != null ? tree.root.left.nextRight.data : -1;         Console.WriteLine("nextRight of " + tree.root.left.data + " is " + b);         int c = tree.root.right.nextRight != null ? tree.root.right.nextRight.data : -1;         Console.WriteLine("nextRight of " + tree.root.right.data + " is " + c);         int d = tree.root.left.left.nextRight != null ? tree.root.left.left.nextRight.data : -1;         Console.WriteLine("nextRight of " + tree.root.left.left.data + " is " + d);     } }      // This code is contributed by Shrikant13

Output:

Following are populated nextRight pointers in the tree(-1 is printed if there is no nextRight)
nextRight of 10 is -1
nextRight of 8 is 2
nextRight of 2 is -1
nextRight of 3 is -1

Thanks to Dhanya for suggesting this approach.

Time Complexity: O(n)

Why doesn’t method 2 work for trees which are not Complete Binary Trees?
Let us consider following tree as an example. In Method 2, we set the nextRight pointer in pre order fashion. When we are at node 4, we set the nextRight of its children which are 8 and 9 (the nextRight of 4 is already set as node 5). nextRight of 8 will simply be set as 9, but nextRight of 9 will be set as NULL which is incorrect. We can’t set the correct nextRight, because when we set nextRight of 9, we only have nextRight of node 4 and ancestors of node 4, we don’t have nextRight of nodes in right subtree of root.

1
/
2        3
/       /
4   5    6    7
/            /
8   9        10   11

See Connect nodes at same level using constant extra space for more solutions.