    02 July 2020

02 July 2020

02 July 2020

02 July 2020

# It Is Time to join JOB

## Android Language ## .Net Programming ## c# Programming ## Asp .Net ## PHP Programming  ## 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
Friday, 14 July 2017 12:27

### Print level order traversal line by line | Set 1

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 ` `#include ` `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 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

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

Friday, 14 July 2017 03:39

### Swap Numbers Without Using Third Variable Java Example

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.
8. import java.io.IOException;
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
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