Print nodes at k distance from root

search
Sign In
Home
Courses
Hire With Us
Algorithmskeyboard_arrow_down
Data Structureskeyboard_arrow_down
Languageskeyboard_arrow_down
Interview Cornerkeyboard_arrow_down
GATEkeyboard_arrow_down
CS Subjectskeyboard_arrow_down
Studentkeyboard_arrow_down
GBlog
Puzzles
What's New ?
▲
Connect nodes at same level
Last Updated: 14-04-2020
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
Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.
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.

We initialize a node Prev which points at the previous node. While traversing the nodes in the same level we keep track of the previous node and point the nextRight pointer to the current node in every iteration.




Java
import java.util.*; 
import java.io.*; 
class Node { 
    int data; 
    Node left, right, nextRight; 
  
    Node(int item) 
    { 
        data = item; 
        left = right = nextRight = null; 
    } 
} 
  
public class BinaryTree { 
    Node root; 
    void connect(Node p) 
    { 
        // initialize queue to hold nodes at same level  
        Queue<Node> q = new LinkedList<>(); 
  
        q.add(root); // adding nodes to tehe queue 
  
        Node temp = null; // initializing prev to null 
        while (!q.isEmpty()) { 
            int n = q.size(); 
            for (int i = 0; i < n; i++) { 
                Node prev = temp; 
                temp = q.poll(); 
  
                // i > 0 because when i is 0 prev points 
                // the last node of previous level,  
                // so we skip it 
                if (i > 0) 
                    prev.nextRight = temp;  
  
                if (temp.left != null) 
                    q.add(temp.left); 
  
                if (temp.right != null) 
                    q.add(temp.right); 
            } 
  
            // pointing last node of the nth level to null 
            temp.nextRight = null;  
        } 
    } 
  
    // 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 Rahul Shakya 
C#
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
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++
C
Java
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)