Study Anytime Any Where We Will Open The Knowledge For You Anish Sir 24x7 Learning solution It Is Time to join JOB
19 September 2020

Study Anytime Any Where

19 September 2020

We Will Open The Knowledge For You

19 September 2020

Anish Sir 24x7 Learning solution

19 September 2020

It Is Time to join JOB

C Programming

C++ Programming

JAVA Programming

Android Language

Android-logo.png

.Net Programming

net-logo-b55c217213ae49991589ed43d7ed58a7.png

c# Programming

photo_1389636992_quiz_image_temp.png

Asp .Net

asplogo-square.png

PHP Programming

58481791cef1014c0b5e4994.png

Search Your Topic

config
Anish Sir

Anish Sir

"I am delighted once again to pen the welcome note to the Tosh!Yas Technologies ."

 Call +91 74 88 34 7779  | Email : anishsingh@live.com

Website URL: http://toshiyas.in

Given a binary tree, print level order traversal in a way that nodes of all levels are printed in separate lines.

For example consider the following tree

          1
       /     \
      2       3
    /   \       \
   4     5       6
        /  \     /
       7    8   9

Output for above tree should be
1
2 3
4 5 6
7 8 9
/* Function to line by line print level order traversal a tree*/
void printLevelOrder(struct node* root)
{
    int h = height(root);
    int i;
    for (i=1; i<=h; i++)
    {
        printGivenLevel(root, i);
        printf("\n");
    }
}
 
/* Print nodes at a given level */
void printGivenLevel(struct node* root, int level)
{
    if (root == NULL)
        return;
    if (level == 1)
        printf("%d ", root->data);
    else if (level > 1)
    {
        printGivenLevel(root->left, level-1);
        printGivenLevel(root->right, level-1);
    }
}

The time complexity of the above solution is O(n2)

How to modify the iterative level order traversal (Method 2 of this) to levels line by line?
The idea is similar to this post. We count the nodes at current level. And for every node, we enqueue its children to queue.

/* Iterative program to print levels line by line */
#include <iostream>
#include <queue>
using namespace std;
 
// A Binary Tree Node
struct node
{
    struct node *left;
    int data;
    struct node *right;
};
 
// Iterative method to do level order traversal line by line
void printLevelOrder(node *root)
{
    // Base Case
    if (root == NULL)  return;
 
    // Create an empty queue for level order tarversal
    queue<node *> q;
 
    // Enqueue Root and initialize height
    q.push(root);
 
    while (1)
    {
        // nodeCount (queue size) indicates number of nodes
        // at current lelvel.
        int nodeCount = q.size();
        if (nodeCount == 0)
            break;
 
        // Dequeue all nodes of current level and Enqueue all
        // nodes of next level
        while (nodeCount > 0)
        {
            node *node = q.front();
            cout << node->data << " ";
            q.pop();
            if (node->left != NULL)
                q.push(node->left);
            if (node->right != NULL)
                q.push(node->right);
            nodeCount--;
        }
        cout << endl;
    }
}
 
// Utility function to create a new tree node
node* newNode(int data)
{
    node *temp = new node;
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
 
// Driver program to test above functions
int main()
{
    // Let us create binary tree shown in above diagram
    node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->right = newNode(6);
 
    printLevelOrder(root);
    return 0;
}

Output:

1
2 3
4 5 6
Friday, 14 July 2017 12:23

Level Order Tree Traversal

Level order traversal of a tree is breadth first traversal for the tree.

Example Tree

Example Tree

Level order traversal of the above tree is 1 2 3 4 5

METHOD 1 (Use function to print a given level)

Algorithm:
There are basically two functions in this method. One is to print all nodes at a given level (printGivenLevel), and other is to print level order traversal of the tree (printLevelorder). printLevelorder makes use of printGivenLevel to print nodes at all levels one by one starting from root.

/*Function to print level order traversal of tree*/
printLevelorder(tree)
for d = 1 to height(tree)
   printGivenLevel(tree, d);

/*Function to print all nodes at a given level*/
printGivenLevel(tree, level)
if tree is NULL then return;
if level is 1, then
    print(tree->data);
else if level greater than 1, then
    printGivenLevel(tree->left, level-1);
    printGivenLevel(tree->right, level-1);
// Recursive C program for level order traversal of Binary Tree
#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node* left, *right;
};
 
/* Function protoypes */
void printGivenLevel(struct node* root, int level);
int height(struct node* node);
struct node* newNode(int data);
 
/* Function to print level order traversal a tree*/
void printLevelOrder(struct node* root)
{
    int h = height(root);
    int i;
    for (i=1; i<=h; i++)
        printGivenLevel(root, i);
}
 
/* Print nodes at a given level */
void printGivenLevel(struct node* root, int level)
{
    if (root == NULL)
        return;
    if (level == 1)
        printf("%d ", root->data);
    else if (level > 1)
    {
        printGivenLevel(root->left, level-1);
        printGivenLevel(root->right, level-1);
    }
}
 
/* Compute the "height" of a tree -- the number of
    nodes along the longest path from the root node
    down to the farthest leaf node.*/
int height(struct node* node)
{
    if (node==NULL)
        return 0;
    else
    {
        /* compute the height of each subtree */
        int lheight = height(node->left);
        int rheight = height(node->right);
 
        /* use the larger one */
        if (lheight > rheight)
            return(lheight+1);
        else return(rheight+1);
    }
}
 
/* 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;
 
    return(node);
}
 
/* Driver program to test above functions*/
int main()
{
    struct node *root = newNode(1);
    root->left        = newNode(2);
    root->right       = newNode(3);
    root->left->left  = newNode(4);
    root->left->right = newNode(5);
 
    printf("Level Order traversal of binary tree is \n");
    printLevelOrder(root);
 
    return 0;
}
Output:
Level order traversal of binary tree is - 
1 2 3 4 5 

Time Complexity: O(n^2) in worst case. For a skewed tree, printGivenLevel() takes O(n) time where n is the number of nodes in the skewed tree. So time complexity of printLevelOrder() is O(n) + O(n-1) + O(n-2) + .. + O(1) which is O(n^2).

METHOD 2 (Use Queue)

Algorithm:
For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.

printLevelorder(tree)
1) Create an empty queue q
2) temp_node = root /*start from root*/
3) Loop while temp_node is not NULL
    a) print temp_node->data.
    b) Enqueue temp_node’s children (first left then right children) to q
    c) Dequeue a node from q and assign it’s value to temp_node

Implementation:
Here is a simple implementation of the above algorithm. Queue is implemented using an array with maximum size of 500. We can implement queue as linked list also.

// Iterative Queue based C program to do level order traversal
// of Binary Tree
#include <stdio.h>
#include <stdlib.h>
#define MAX_Q_SIZE 500
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
 
/* frunction prototypes */
struct node** createQueue(int *, int *);
void enQueue(struct node **, int *, struct node *);
struct node *deQueue(struct node **, int *);
 
/* Given a binary tree, print its nodes in level order
   using array for implementing queue */
void printLevelOrder(struct node* root)
{
    int rear, front;
    struct node **queue = createQueue(&front, &rear);
    struct node *temp_node = root;
 
    while (temp_node)
    {
        printf("%d ", temp_node->data);
 
        /*Enqueue left child */
        if (temp_node->left)
            enQueue(queue, &rear, temp_node->left);
 
        /*Enqueue right child */
        if (temp_node->right)
            enQueue(queue, &rear, temp_node->right);
 
        /*Dequeue node and make it temp_node*/
        temp_node = deQueue(queue, &front);
    }
}
 
/*UTILITY FUNCTIONS*/
struct node** createQueue(int *front, int *rear)
{
    struct node **queue =
        (struct node **)malloc(sizeof(struct node*)*MAX_Q_SIZE);
 
    *front = *rear = 0;
    return queue;
}
 
void enQueue(struct node **queue, int *rear, struct node *new_node)
{
    queue[*rear] = new_node;
    (*rear)++;
}
 
struct node *deQueue(struct node **queue, int *front)
{
    (*front)++;
    return queue[*front - 1];
}
 
/* 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;
 
    return(node);
}
 
/* Driver program to test above functions*/
int main()
{
    struct node *root = newNode(1);
    root->left        = newNode(2);
    root->right       = newNode(3);
    root->left->left  = newNode(4);
    root->left->right = newNode(5);
 
    printf("Level Order traversal of binary tree is \n");
    printLevelOrder(root);
 
    return 0;

 

}
Output:
Level order traversal of binary tree is - 
1 2 3 4 5 

Time Complexity: O(n) where n is number of nodes in the binary tree

 

  1. /*
  2.         Swap Numbers Without Using Third Variable Java Example
  3.         This Swap Numbers Java Example shows how to
  4.         swap value of two numbers without using third variable using java.
  5. */
  6.  
  7. public class SwapElementsWithoutThirdVariableExample {
  8.  
  9.         public static void main(String[] args) {
  10.                
  11.                 int num1 = 10;
  12.                 int num2 = 20;
  13.                
  14.                 System.out.println("Before Swapping");
  15.                 System.out.println("Value of num1 is :" + num1);
  16.                 System.out.println("Value of num2 is :" +num2);
  17.                
  18.                 //add both the numbers and assign it to first
  19.                 num1 = num1 + num2;
  20.                 num2 = num1 - num2;
  21.                 num1 = num1 - num2;
  22.                
  23.                 System.out.println("Before Swapping");
  24.                 System.out.println("Value of num1 is :" + num1);
  25.                 System.out.println("Value of num2 is :" +num2);
  26.         }
  27.  
  28.  
  29. }
  30.  
  31. /*
  32. Output of Swap Numbers Without Using Third Variable example would be
  33. Before Swapping
  34. Value of num1 is :10
  35. Value of num2 is :20
  36. Before Swapping
  37. Value of num1 is :20
  38. Value of num2 is :10
  39. */
Friday, 14 July 2017 03:38

Swap Numbers Java Example

  1. /*
  2.         Swap Numbers Java Example
  3.         This Swap Numbers Java Example shows how to
  4.         swap value of two numbers using java.
  5. */
  6.  
  7. public class SwapElementsExample {
  8.  
  9.         public static void main(String[] args) {
  10.                
  11.                 int num1 = 10;
  12.                 int num2 = 20;
  13.                
  14.                 System.out.println("Before Swapping");
  15.                 System.out.println("Value of num1 is :" + num1);
  16.                 System.out.println("Value of num2 is :" +num2);
  17.                
  18.                 //swap the value
  19.                 swap(num1, num2);
  20.         }
  21.  
  22.         private static void swap(int num1, int num2) {
  23.                
  24.                 int temp = num1;
  25.                 num1 = num2;
  26.                 num2 = temp;
  27.                
  28.                 System.out.println("After Swapping");
  29.                 System.out.println("Value of num1 is :" + num1);
  30.                 System.out.println("Value of num2 is :" +num2);
  31.                
  32.         }
  33. }
  34.  
  35. /*
  36. Output of Swap Numbers example would be
  37. Before Swapping
  38. Value of num1 is :10
  39. Value of num2 is :20
  40. After Swapping
  41. Value of num1 is :20
  42. Value of num2 is :10
  43. */
Friday, 14 July 2017 03:37

Reverse Number using Java

  1. /*
  2.   Reverse Number using Java
  3.   This Java Reverse Number Example shows how to reverse a given number.
  4. */
  5.  
  6. public class ReverseNumber {
  7.  
  8.         public static void main(String[] args) {
  9.                
  10.                 //original number
  11.                 int number = 1234;
  12.                 int reversedNumber = 0;
  13.                 int temp = 0;
  14.                
  15.                 while(number > 0){
  16.                        
  17.                         //use modulus operator to strip off the last digit
  18.                         temp = number%10;
  19.                        
  20.                         //create the reversed number
  21.                         reversedNumber = reversedNumber * 10 + temp;
  22.                         number = number/10;
  23.                          
  24.                 }
  25.                
  26.                 //output the reversed number
  27.                 System.out.println("Reversed Number is: " + reversedNumber);
  28.         }
  29. }
  30.  
  31. /*
  32. Output of this Number Reverse program would be
  33. Reversed Number is: 4321
  34. */
Friday, 14 July 2017 03:36

Java Interface Example

  1. /*
  2. Java Interface example.
  3. This Java Interface example describes how interface is defined and
  4. being used in Java language.
  5.  
  6. Syntax of defining java interface is,
  7. <modifier> interface <interface-name>{
  8.   //members and methods()
  9. }
  10. */
  11.  
  12. //declare an interface
  13. interface IntExample{
  14.  
  15.   /*
  16.   Syntax to declare method in java interface is,
  17.   <modifier> <return-type> methodName(<optional-parameters>);
  18.   IMPORTANT : Methods declared in the interface are implicitly public and abstract.
  19.   */
  20.  
  21.   public void sayHello();
  22.   }
  23. }
  24. /*
  25. Classes are extended while interfaces are implemented.
  26. To implement an interface use implements keyword.
  27. IMPORTANT : A class can extend only one other class, while it
  28. can implement n number of interfaces.
  29. */
  30.  
  31. public class JavaInterfaceExample implements IntExample{
  32.   /*
  33.   We have to define the method declared in implemented interface,
  34.   or else we have to declare the implementing class as abstract class.
  35.   */
  36.  
  37.   public void sayHello(){
  38.     System.out.println("Hello Visitor !");
  39.   }
  40.  
  41.   public static void main(String args[]){
  42.     //create object of the class
  43.     JavaInterfaceExample javaInterfaceExample = new JavaInterfaceExample();
  44.     //invoke sayHello(), declared in IntExample interface.
  45.     javaInterfaceExample.sayHello();
  46.   }
  47. }
  48.  
  49. /*
  50. OUTPUT of the above given Java Interface example would be :
  51. Hello Visitor !
  52. */
Friday, 14 July 2017 03:35

Java Factorial Using Recursion Example

  1. *
  2.         Java Factorial Using Recursion Example
  3.         This Java example shows how to generate factorial of a given number
  4.         using recursive function.
  5. */
  6.  
  7. import java.io.BufferedReader;
  8. import java.io.IOException;
  9. import java.io.InputStreamReader;
  10.  
  11. public class JavaFactorialUsingRecursion {
  12.        
  13.         public static void main(String args[]) throws NumberFormatExceptionIOException{
  14.                
  15.                 System.out.println("Enter the number: ");
  16.                
  17.                 //get input from the user
  18.                 BufferedReader br=new BufferedReader(newInputStreamReader(System.in));
  19.                 int a = Integer.parseInt(br.readLine());
  20.                
  21.                 //call the recursive function to generate factorial
  22.                 int result= fact(a);
  23.                
  24.                
  25.                 System.out.println("Factorial of the number is: " + result);
  26.         }
  27.        
  28.         static int fact(int b)
  29.         {
  30.                 if(<= 1)
  31.                         //if the number is 1 then return 1
  32.                         return 1;
  33.                 else
  34.                         //else call the same function with the value - 1
  35.                         return b * fact(b-1);
  36.         }
  37. }
  38.  
  39. /*
  40. Output of this Java example would be
  41.  
  42. Enter the number:
  43. 5
  44. Factorial of the number is: 120
  45. */
Friday, 14 July 2017 03:34

Java Factorial Example

  1. /*
  2.   Java Factorial Example
  3.   This Java Factorial Example shows how to calculate factorial of
  4.   a given number using Java.
  5. */
  6.  
  7. public class NumberFactorial {
  8.  
  9.         public static void main(String[] args) {
  10.                
  11.                 int number = 5;
  12.                
  13.                 /*
  14.                  * Factorial of any number is !n.
  15.                  * For example, factorial of 4 is 4*3*2*1.
  16.                 */
  17.                
  18.                 int factorial = number;
  19.                
  20.                 for(int i =(number - 1); i > 1; i--)
  21.                 {
  22.                         factorial = factorial * i;
  23.                 }
  24.        
  25.                 System.out.println("Factorial of a number is " + factorial);
  26.         }
  27. }
  28.  
  29. /*
  30. Output of the Factorial program would be
  31. Factorial of a number is 120
  32. */
Friday, 14 July 2017 03:33

Java Class Example

  1. /*
  2. Java Class example.
  3. This Java class example describes how class is defined and being used
  4. in Java language.
  5.  
  6. Syntax of defining java class is,
  7. <modifier> class <class-name>{
  8.   // members and methods
  9. }
  10. */
  11.  
  12. public class JavaClassExample{
  13.   /*
  14.   Syntax of defining memebers of the java class is,
  15.     <modifier> type <name>;
  16.   */
  17.   private String name;
  18.   /*
  19.   Syntax of defining methods of the java class is,
  20.   <modifier> <return-type> methodName(<optional-parameter-list>) <exception-list>{
  21.                     ...
  22.   }
  23.   */
  24.   public void setName(String n){
  25.     //set passed parameter as name
  26.     name = n;
  27.   }
  28.   public String getName(){
  29.     //return the set name
  30.     return name;
  31.   }
  32.   //main method will be called first when program is executed
  33.   public static void main(String args[]){
  34.     /*
  35.     Syntax of java object creation is,
  36.     <class-name> object-name = new <class-constructor>;
  37.     */
  38.     JavaClassExample javaClassExample = new JavaClassExample();
  39.     //set name member of this object
  40.     javaClassExample.setName("Visitor");
  41.     // print the name
  42.     System.out.println("Hello " + javaClassExample.getName());      
  43.   }
  44. }
  45.  
  46. /*
  47. OUTPUT of the above given Java Class Example would be :
  48. Hello Visitor
  49. */
Friday, 14 July 2017 03:32

Hello World example

  1. /*
  2. Java Hello World example.
  3. */
  4.  
  5. public class HelloWorldExample{
  6.  
  7.   public static void main(String args[]){
  8.  
  9.     /*
  10.     Use System.out.println() to print on console.
  11.     */
  12.     System.out.println("Hello World !");
  13.  
  14.   }
  15.  
  16. }
  17.  
  18. /*
  19.  
  20. OUTPUT of the above given Java Hello World Example would be :
  21.  
  22. Hello World !
  23.  
  24. */
Page 10 of 32