Print nodes at k distance from root | Iterative
Given a root of a tree, and an integer k. Print all the nodes which are at k distance from root.
Example :
Input : 20 / \ 10 30 / \ / \ 5 15 25 40 / 12 and k = 3 Root is at level 1. Output : 5 15 25 40
Recursive approach to this problem is discussed here
Following is the iterative approach.
The solution is similar to Getting level of node in Binary Tree
Implementation:
C++
// CPP program to print all nodes of level k // iterative approach /* binary tree root is at level 1 20 / \ 10 30 / \ / \ 5 15 25 40 / 12 */ #include <bits/stdc++.h> using namespace std; // Node of binary tree struct Node { int data; Node* left, * right; }; // Function to add a new node Node* newNode( int data) { Node* newnode = new Node(); newnode->data = data; newnode->left = newnode->right = NULL; } // Function to print nodes of given level bool printKDistant(Node* root, int klevel) { queue<Node*> q; int level = 1; bool flag = false ; q.push(root); // extra NULL is pushed to keep track // of all the nodes to be pushed before // level is incremented by 1 q.push(NULL); while (!q.empty()) { Node* temp = q.front(); // print when level is equal to k if (level == klevel && temp != NULL) { flag = true ; cout << temp->data << " " ; } q.pop(); if (temp == NULL) { if (q.front()) q.push(NULL); level += 1; // break the loop if level exceeds // the given level number if (level > klevel) break ; } else { if (temp->left) q.push(temp->left); if (temp->right) q.push(temp->right); } } cout << endl; return flag; } // Driver code int main() { // create a binary tree Node* root = newNode(20); root->left = newNode(10); root->right = newNode(30); root->left->left = newNode(5); root->left->right = newNode(15); root->left->right->left = newNode(12); root->right->left = newNode(25); root->right->right = newNode(40); cout << "data at level 1 : " ; int ret = printKDistant(root, 1); if (ret == false ) cout << "Number exceeds total number of levels\n" ; cout << "data at level 2 : " ; ret = printKDistant(root, 2); if (ret == false ) cout << "Number exceeds total number of levels\n" ; cout << "data at level 3 : " ; ret = printKDistant(root, 3); if (ret == false ) cout << "Number exceeds total number of levels\n" ; cout << "data at level 6 : " ; ret = printKDistant(root, 6); if (ret == false ) cout << "Number exceeds total number of levels\n" ; return 0; } |
Java
// Java program to print all nodes of level k // iterative approach /* binary tree root is at level 1 20 / \ 10 30 / \ / \ 5 15 25 40 / 12 */ import java.util.*; class GFG { // Node of binary tree static class Node { int data; Node left, right; } // Function to add a new node static Node newNode( int data) { Node newnode = new Node(); newnode.data = data; newnode.left = newnode.right = null ; return newnode; } // Function to print nodes of given level static boolean printKDistant(Node root, int klevel) { Queue<Node> q = new LinkedList<>(); int level = 1 ; boolean flag = false ; q.add(root); // extra null is added to keep track // of all the nodes to be added before // level is incremented by 1 q.add( null ); while (q.size() > 0 ) { Node temp = q.peek(); // print when level is equal to k if (level == klevel && temp != null ) { flag = true ; System.out.print( temp.data + " " ); } q.remove(); if (temp == null ) { if (q.peek() != null ) q.add( null ); level += 1 ; // break the loop if level exceeds // the given level number if (level > klevel) break ; } else { if (temp.left != null ) q.add(temp.left); if (temp.right != null ) q.add(temp.right); } } System.out.println(); return flag; } // Driver code public static void main(String srga[]) { // create a binary tree Node root = newNode( 20 ); root.left = newNode( 10 ); root.right = newNode( 30 ); root.left.left = newNode( 5 ); root.left.right = newNode( 15 ); root.left.right.left = newNode( 12 ); root.right.left = newNode( 25 ); root.right.right = newNode( 40 ); System.out.print( "data at level 1 : " ); boolean ret = printKDistant(root, 1 ); if (ret == false ) System.out.print( "Number exceeds total " + "number of levels\n" ); System.out.print( "data at level 2 : " ); ret = printKDistant(root, 2 ); if (ret == false ) System.out.print( "Number exceeds total " + "number of levels\n" ); System.out.print( "data at level 3 : " ); ret = printKDistant(root, 3 ); if (ret == false ) System.out.print( "Number exceeds total " + "number of levels\n" ); System.out.print( "data at level 6 : " ); ret = printKDistant(root, 6 ); if (ret == false ) System.out.print( "Number exceeds total" + "number of levels\n" ); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 program to print all nodes of level k # iterative approach """ binary tree root is at level 1 20 / \ 10 30 / \ / \ 5 15 25 40 / 12 """ # Node of binary tree # Function to add a new node class newNode: def __init__( self , data): self .data = data self .left = self .right = None # Function to print nodes of given level def printKDistant( root, klevel): q = [] level = 1 flag = False q.append(root) # extra None is appended to keep track # of all the nodes to be appended # before level is incremented by 1 q.append( None ) while ( len (q)): temp = q[ 0 ] # print when level is equal to k if (level = = klevel and temp ! = None ): flag = True print (temp.data, end = " " ) q.pop( 0 ) if (temp = = None ) : if ( len (q)): q.append( None ) level + = 1 # break the loop if level exceeds # the given level number if (level > klevel) : break else : if (temp.left) : q.append(temp.left) if (temp.right) : q.append(temp.right) print () return flag # Driver Code if __name__ = = '__main__' : root = newNode( 20 ) root.left = newNode( 10 ) root.right = newNode( 30 ) root.left.left = newNode( 5 ) root.left.right = newNode( 15 ) root.left.right.left = newNode( 12 ) root.right.left = newNode( 25 ) root.right.right = newNode( 40 ) print ( "data at level 1 : " , end = "") ret = printKDistant(root, 1 ) if (ret = = False ): print ( "Number exceeds total" , "number of levels" ) print ( "data at level 2 : " , end = "") ret = printKDistant(root, 2 ) if (ret = = False ) : print ( "Number exceeds total" , "number of levels" ) print ( "data at level 3 : " , end = "") ret = printKDistant(root, 3 ) if (ret = = False ) : print ( "Number exceeds total" , "number of levels" ) print ( "data at level 6 : " , end = "") ret = printKDistant(root, 6 ) if (ret = = False ): print ( "Number exceeds total number of levels" ) # This code is contributed # by SHUBHAMSINGH10 |
C#
// C# program to print all nodes of level k // iterative approach /* binary tree root is at level 1 20 / \ 10 30 / \ / \ 5 15 25 40 / 12 */ using System; using System.Collections.Generic; class GFG { // Node of binary tree public class Node { public int data; public Node left, right; } // Function to add a new node static Node newNode( int data) { Node newnode = new Node(); newnode.data = data; newnode.left = newnode.right = null ; return newnode; } // Function to print nodes of given level static Boolean printKDistant(Node root, int klevel) { Queue<Node> q = new Queue<Node>(); int level = 1; Boolean flag = false ; q.Enqueue(root); // extra null is added to keep track // of all the nodes to be added before // level is incremented by 1 q.Enqueue( null ); while (q.Count > 0) { Node temp = q.Peek(); // print when level is equal to k if (level == klevel && temp != null ) { flag = true ; Console.Write( temp.data + " " ); } q.Dequeue(); if (temp == null ) { if (q.Count > 0&&q.Peek() != null ) q.Enqueue( null ); level += 1; // break the loop if level exceeds // the given level number if (level > klevel) break ; } else { if (temp.left != null ) q.Enqueue(temp.left); if (temp.right != null ) q.Enqueue(temp.right); } } Console.Write( "\n" ); return flag; } // Driver code public static void Main(String []srga) { // create a binary tree Node root = newNode(20); root.left = newNode(10); root.right = newNode(30); root.left.left = newNode(5); root.left.right = newNode(15); root.left.right.left = newNode(12); root.right.left = newNode(25); root.right.right = newNode(40); Console.Write( "data at level 1 : " ); Boolean ret = printKDistant(root, 1); if (ret == false ) Console.Write( "Number exceeds total " + "number of levels\n" ); Console.Write( "data at level 2 : " ); ret = printKDistant(root, 2); if (ret == false ) Console.Write( "Number exceeds total " + "number of levels\n" ); Console.Write( "data at level 3 : " ); ret = printKDistant(root, 3); if (ret == false ) Console.Write( "Number exceeds total " + "number of levels\n" ); Console.Write( "data at level 6 : " ); ret = printKDistant(root, 6); if (ret == false ) Console.Write( "Number exceeds total" + "number of levels\n" ); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to print all nodes of level k // iterative approach /* binary tree root is at level 1 20 / \ 10 30 / \ / \ 5 15 25 40 / 12 */ class Node { constructor(data) { this .left = null ; this .right = null ; this .data = data; } } // Function to add a new node function newNode(data) { let newnode = new Node(data); return newnode; } // Function to print nodes of given level function printKDistant(root, klevel) { let q = []; let level = 1; let flag = false ; q.push(root); // extra null is added to keep track // of all the nodes to be added before // level is incremented by 1 q.push( null ); while (q.length > 0) { let temp = q[0]; // print when level is equal to k if (level == klevel && temp != null ) { flag = true ; document.write( temp.data + " " ); } q.shift(); if (temp == null ) { if (q[0] != null ) q.push( null ); level += 1; // break the loop if level exceeds // the given level number if (level > klevel) break ; } else { if (temp.left != null ) q.push(temp.left); if (temp.right != null ) q.push(temp.right); } } document.write( "</br>" ); return flag; } // create a binary tree let root = newNode(20); root.left = newNode(10); root.right = newNode(30); root.left.left = newNode(5); root.left.right = newNode(15); root.left.right.left = newNode(12); root.right.left = newNode(25); root.right.right = newNode(40); document.write( "data at level 1 : " ); let ret = printKDistant(root, 1); if (ret == false ) document.write( "Number exceeds total " + "number of levels" + "</br>" ); document.write( "data at level 2 : " ); ret = printKDistant(root, 2); if (ret == false ) document.write( "Number exceeds total " + "number of levels" + "</br>" ); document.write( "data at level 3 : " ); ret = printKDistant(root, 3); if (ret == false ) document.write( "Number exceeds total " + "number of levels" + "</br>" ); document.write( "data at level 6 : " ); ret = printKDistant(root, 6); if (ret == false ) document.write( "Number exceeds total" + "number of levels" + "</br>" ); // This code is contributed by suresh07. </script> |
Output
data at level 1 : 20 data at level 2 : 10 30 data at level 3 : 5 15 25 40 data at level 6 : Number exceeds total number of levels
Time Complexity: O(n) where n = Number of nodes
Space Complexity: O(n)