## Print all nodes at distance k from a given node

Given a binary tree, a target node in the binary tree, and an integer value k, print all the nodes that are at distance k from the given target node. No parent pointers are available.

```Consider the tree shown in diagram

Input: target = pointer to node with data 8.
root = pointer to node with data 20.
k = 2.
Output : 10 14 22

If target is 14 and k is 3, then output
should be "4 20"

```

There are two types of nodes to be considered.
1) Nodes in the subtree rooted with target node. For example if the target node is 8 and k is 2, then such nodes are 10 and 14.
2) Other nodes, may be an ancestor of target, or a node in some other subtree. For target node 8 and k is 2, the node 22 comes in this category.

Finding the first type of nodes is easy to implement. Just traverse subtrees rooted with the target node and decrement k in recursive call. When the k becomes 0, print the node currently being traversed . Here we call the function as printkdistanceNodeDown().

How to find nodes of second type? For the output nodes not lying in the subtree with the target node as the root, we must go through all ancestors. For every ancestor, we find its distance from target node, let the distance be d, now we go to other subtree (if target was found in left subtree, then we go to right subtree and vice versa) of the ancestor and find all nodes at k-d distance from the ancestor.

Following is the implementation of the above approach.

`#include <iostream>`
`using` `namespace` `std;`
`// A binary Tree node`
`struct` `node`
`{`
`    ``int` `data;`
`    ``struct` `node *left, *right;`
`};`
`/* Recursive function to print all the nodes at distance k in the`
`   ``tree (or subtree) rooted with given root. See  */`
`void` `printkdistanceNodeDown(node *root, ``int` `k)`
`{`
`    ``// Base Case`
`    ``if` `(root == NULL || k < 0)  ``return``;`
`    ``// If we reach a k distant node, print it`
`    ``if` `(k==0)`
`    ``{`
`        ``cout << root->data << endl;`
`        ``return``;`
`    ``}`
`    ``// Recur for left and right subtrees`
`    ``printkdistanceNodeDown(root->left, k-1);`
`    ``printkdistanceNodeDown(root->right, k-1);`
`}`
`// Prints all nodes at distance k from a given target node.`
`// The k distant nodes may be upward or downward.  This function`
`// Returns distance of root from target node, it returns -1 if target`
`// node is not present in tree rooted with root.`
`int` `printkdistanceNode(node* root, node* target , ``int` `k)`
`{`
`    ``// Base Case 1: If tree is empty, return -1`
`    ``if` `(root == NULL) ``return` `-1;`
`    ``// If target is same as root.  Use the downward function`
`    ``// to print all nodes at distance k in subtree rooted with`
`    ``// target or root`
`    ``if` `(root == target)`
`    ``{`
`        ``printkdistanceNodeDown(root, k);`
`        ``return` `0;`
`    ``}`
`    ``// Recur for left subtree`
`    ``int` `dl = printkdistanceNode(root->left, target, k);`
`    ``// Check if target node was found in left subtree`
`    ``if` `(dl != -1)`
`    ``{`
`         ``// If root is at distance k from target, print root`
`         ``// Note that dl is Distance of root's left child from target`
`         ``if` `(dl + 1 == k)`
`            ``cout << root->data << endl;`
`         ``// Else go to right subtree and print all k-dl-2 distant nodes`
`         ``// Note that the right child is 2 edges away from left child`
`         ``else`
`            ``printkdistanceNodeDown(root->right, k-dl-2);`
`         ``// Add 1 to the distance and return value for parent calls`
`         ``return` `1 + dl;`
`    ``}`
`    ``// MIRROR OF ABOVE CODE FOR RIGHT SUBTREE`
`    ``// Note that we reach here only when node was not found in left subtree`
`    ``int` `dr = printkdistanceNode(root->right, target, k);`
`    ``if` `(dr != -1)`
`    ``{`
`         ``if` `(dr + 1 == k)`
`            ``cout << root->data << endl;`
`         ``else`
`            ``printkdistanceNodeDown(root->left, k-dr-2);`
`         ``return` `1 + dr;`
`    ``}`
`    ``// If target was neither present in left nor in right subtree`
`    ``return` `-1;`
`}`
`// A utility function to create a new binary tree node`
`node *newnode(``int` `data)`
`{`
`    ``node *temp = ``new` `node;`
`    ``temp->data = data;`
`    ``temp->left = temp->right = NULL;`
`    ``return` `temp;`
`}`
`// Driver program to test above functions`
`int` `main()`
`{`
`    ``/* Let us construct the tree shown in above diagram */`
`    ``node * root = newnode(20);`
`    ``root->left = newnode(8);`
`    ``root->right = newnode(22);`
`    ``root->left->left = newnode(4);`
`    ``root->left->right = newnode(12);`
`    ``root->left->right->left = newnode(10);`
`    ``root->left->right->right = newnode(14);`
`    ``node * target = root->left->right;`
`    ``printkdistanceNode(root, target, 2);`
`    ``return` `0;`
`}`

Output:

```4
20```

Time Complexity: At first look the time complexity looks more than O(n), but if we take a closer look, we can observe that no node is traversed more than twice. Therefore the time complexity is O(n).

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Check if a given Binary Tree is height balanced like a Red-Black Tree

In a Red-Black Tree, the maximum height of a node is at most twice the minimum height (The four Red-Black tree properties make sure this is always followed). Given a Binary Search Tree, we need to check for following property.
For every node, length of the longest leaf to node path has not more than twice the nodes on shortest path from node to leaf.

```    12                                        40
\                                     /    \
14                                 10      100
\                                        /  \
16                                     60   150
Cannot be a Red-Black Tree              It can be Red-Black Tree
with any color assignment
Max height of 12 is 1
Min height of 12 is 3

10
/   \
5     100
/   \
50   150
/
40
It can also be Red-Black Tree
```

Expected time complexity is O(n). The tree should be traversed at-most once in the solution.

We strongly recommend to minimize the browser and try this yourself first.
For every node, we need to get the maximum and minimum heights and compare them. The idea is to traverse the tree and for every node check if it’s balanced. We need to write a recursive function that returns three things, a boolean value to indicate the tree is balanced or not, minimum height and maximum height. To return multiple values, we can either use a structure or pass variables by reference. We have passed maxh and minh by reference so that the values can be used in parent calls.

`/* Program to check if a given Binary Tree is balanced like a Red-Black Tree */`
`#include <iostream>`
`using` `namespace` `std;`
`struct` `Node`
`{`
`    ``int` `key;`
`    ``Node *left, *right;`
`};`
`/* utility that allocates a new Node with the given key  */`
`Node* newNode(``int` `key)`
`{`
`    ``Node* node = ``new` `Node;`
`    ``node->key = key;`
`    ``node->left = node->right = NULL;`
`    ``return` `(node);`
`}`
`// Returns returns tree if the Binary tree is balanced like a Red-Black`
`// tree. This function also sets value in maxh and minh (passed by`
`// reference). maxh and minh are set as maximum and minimum heights of root.`
`bool` `isBalancedUtil(Node *root, ``int` `&maxh, ``int` `&minh)`
`{`
`    ``// Base case`
`    ``if` `(root == NULL)`
`    ``{`
`        ``maxh = minh = 0;`
`        ``return` `true``;`
`    ``}`
`    ``int` `lmxh, lmnh; ``// To store max and min heights of left subtree`
`    ``int` `rmxh, rmnh; ``// To store max and min heights of right subtree`
`    ``// Check if left subtree is balanced, also set lmxh and lmnh`
`    ``if` `(isBalancedUtil(root->left, lmxh, lmnh) == ``false``)`
`        ``return` `false``;`
`    ``// Check if right subtree is balanced, also set rmxh and rmnh`
`    ``if` `(isBalancedUtil(root->right, rmxh, rmnh) == ``false``)`
`        ``return` `false``;`
`    ``// Set the max and min heights of this node for the parent call`
`    ``maxh = max(lmxh, rmxh) + 1;`
`    ``minh = min(lmnh, rmnh) + 1;`
`    ``// See if this node is balanced`
`    ``if` `(maxh <= 2*minh)`
`        ``return` `true``;`
`    ``return` `false``;`
`}`
`// A wrapper over isBalancedUtil()`
`bool` `isBalanced(Node *root)`
`{`
`    ``int` `maxh, minh;`
`    ``return` `isBalancedUtil(root, maxh, minh);`
`}`
`/* Driver program to test above functions*/`
`int` `main()`
`{`
`    ``Node * root = newNode(10);`
`    ``root->left = newNode(5);`
`    ``root->right = newNode(100);`
`    ``root->right->left = newNode(50);`
`    ``root->right->right = newNode(150);`
`    ``root->right->left->left = newNode(40);`
`    ``isBalanced(root)? cout << ``"Balanced"` `: cout << ``"Not Balanced"``;`
`    ``return` `0;`
`}`

Output:

`Balanced`

Time Complexity: Time Complexity of above code is O(n) as the code does a simple tree traversal.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Print all nodes that are at distance k from a leaf node

Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node.

Here k distance from a leaf means k levels higher than a leaf node. For example if k is more than height of Binary Tree, then nothing should be printed. Expected time complexity is O(n) where n is the number nodes in the given Binary Tree.

The idea is to traverse the tree. Keep storing all ancestors till we hit a leaf node. When we reach a leaf node, we print the ancestor at distance k. We also need to keep track of nodes that are already printed as output. For that we use a boolean array visited[].

`/* Program to print all nodes which are at distance k from a leaf */`
`#include <iostream>`
`using` `namespace` `std;`
`#define MAX_HEIGHT 10000`
`struct` `Node`
`{`
`    ``int` `key;`
`    ``Node *left, *right;`
`};`
`/* utility that allocates a new Node with the given key  */`
`Node* newNode(``int` `key)`
`{`
`    ``Node* node = ``new` `Node;`
`    ``node->key = key;`
`    ``node->left = node->right = NULL;`
`    ``return` `(node);`
`}`
`/* This function prints all nodes that are distance k from a leaf node`
`   ``path[] --> Store ancestors of a node`
`   ``visited[] --> Stores true if a node is printed as output.  A node may be k`
`                 ``distance away from many leaves, we want to print it once */`
`void` `kDistantFromLeafUtil(Node* node, ``int` `path[], ``bool` `visited[],`
`                          ``int` `pathLen, ``int` `k)`
`{`
`    ``// Base case`
`    ``if` `(node==NULL) ``return``;`
`    ``/* append this Node to the path array */`
`    ``path[pathLen] = node->key;`
`    ``visited[pathLen] = ``false``;`
`    ``pathLen++;`
`    ``/* it's a leaf, so print the ancestor at distance k only`
`       ``if the ancestor is not already printed  */`
`    ``if` `(node->left == NULL && node->right == NULL &&`
`        ``pathLen-k-1 >= 0 && visited[pathLen-k-1] == ``false``)`
`    ``{`
`        ``cout << path[pathLen-k-1] << ``" "``;`
`        ``visited[pathLen-k-1] = ``true``;`
`        ``return``;`
`    ``}`
`    ``/* If not leaf node, recur for left and right subtrees */`
`    ``kDistantFromLeafUtil(node->left, path, visited, pathLen, k);`
`    ``kDistantFromLeafUtil(node->right, path, visited, pathLen, k);`
`}`
`/* Given a binary tree and a nuber k, print all nodes that are k`
`   ``distant from a leaf*/`
`void` `printKDistantfromLeaf(Node* node, ``int` `k)`
`{`
`    ``int` `path[MAX_HEIGHT];`
`    ``bool` `visited[MAX_HEIGHT] = {``false``};`
`    ``kDistantFromLeafUtil(node, path, visited, 0, k);`
`}`
`/* Driver program to test above functions*/`
`int` `main()`
`{`
`    ``// Let us create binary tree given in the above example`
`    ``Node * root = newNode(1);`
`    ``root->left = newNode(2);`
`    ``root->right = newNode(3);`
`    ``root->left->left = newNode(4);`
`    ``root->left->right = newNode(5);`
`    ``root->right->left = newNode(6);`
`    ``root->right->right = newNode(7);`
`    ``root->right->left->right = newNode(8);`
`    ``cout << ``"Nodes at distance 2 are: "``;`
`    ``printKDistantfromLeaf(root, 2);`
`    ``return` `0;`
`}`

Output:

`Nodes at distance 2 are: 3 1`

Time Complexity: Time Complexity of above code is O(n) as the code does a simple tree traversal.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Tree Isomorphism Problem

Write a function to detect if two trees are isomorphic. Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e. by swapping left and right children of a number of nodes. Any number of nodes at any level can have their children swapped. Two empty trees are isomorphic.

For example, following two trees are isomorphic with following sub-trees flipped: 2 and 3, NULL and 6, 7 and 8.

We simultaneously traverse both trees. Let the current internal nodes of two trees being traversed be n1 and n2 respectively. There are following two conditions for subtrees rooted with n1 and n2 to be isomorphic.
1) Data of n1 and n2 is same.
2) One of the following two is true for children of n1 and n2
……a) Left child of n1 is isomorphic to left child of n2 and right child of n1 is isomorphic to right child of n2.
……b) Left child of n1 is isomorphic to right child of n2 and right child of n1 is isomorphic to left child of n2.

`// A C++ program to check if two given trees are isomorphic`
`#include <iostream>`
`using` `namespace` `std;`
`/* A binary tree node has data, pointer to left and right children */`
`struct` `node`
`{`
`    ``int` `data;`
`    ``struct` `node* left;`
`    ``struct` `node* right;`
`};`
`/* Given a binary tree, print its nodes in reverse level order */`
`bool` `isIsomorphic(node* n1, node *n2)`
`{`
` ``// Both roots are NULL, trees isomorphic by definition`
` ``if` `(n1 == NULL && n2 == NULL)`
`    ``return` `true``;`
` ``// Exactly one of the n1 and n2 is NULL, trees not isomorphic`
` ``if` `(n1 == NULL || n2 == NULL)`
`    ``return` `false``;`
` ``if` `(n1->data != n2->data)`
`    ``return` `false``;`
` ``// There are two possible cases for n1 and n2 to be isomorphic`
` ``// Case 1: The subtrees rooted at these nodes have NOT been "Flipped".`
` ``// Both of these subtrees have to be isomorphic, hence the &&`
` ``// Case 2: The subtrees rooted at these nodes have been "Flipped"`
` ``return`
` ``(isIsomorphic(n1->left,n2->left) && isIsomorphic(n1->right,n2->right))||`
` ``(isIsomorphic(n1->left,n2->right) && isIsomorphic(n1->right,n2->left));`
`}`
`/* Helper function that allocates a new node with the`
`   ``given data and NULL left and right pointers. */`
`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 trees shown in above diagram`
`    ``struct` `node *n1 = newNode(1);`
`    ``n1->left        = newNode(2);`
`    ``n1->right       = newNode(3);`
`    ``n1->left->left  = newNode(4);`
`    ``n1->left->right = newNode(5);`
`    ``n1->right->left  = newNode(6);`
`    ``n1->left->right->left = newNode(7);`
`    ``n1->left->right->right = newNode(8);`
`    ``struct` `node *n2 = newNode(1);`
`    ``n2->left         = newNode(3);`
`    ``n2->right        = newNode(2);`
`    ``n2->right->left   = newNode(4);`
`    ``n2->right->right   = newNode(5);`
`    ``n2->left->right   = newNode(6);`
`    ``n2->right->right->left = newNode(8);`
`    ``n2->right->right->right = newNode(7);`
`    ``if` `(isIsomorphic(n1, n2) == ``true``)`
`       ``cout << ``"Yes"``;`
`    ``else`
`      ``cout << ``"No"``;`
`    ``return` `0;`
`}`

Output:

`Yes`

Time Complexity: The above solution does a traversal of both trees. So time complexity is O(m + n) where m and n are number of nodes in given trees.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Custom Tree Problem

You are given a set of links, e.g.

```a ---> b
b ---> c
b ---> d
a ---> e```

Print the tree that would form when each pair of these links that has the same character as start and end point is joined together. You have to maintain fidelity w.r.t. the height of nodes, i.e. nodes at height n from root should be printed at same row or column. For set of links given above, tree printed should be –

```-->a
|-->b
|   |-->c
|   |-->d
|-->e```

Note that these links need not form a single tree; they could form, ahem, a forest. Consider the following links

```a ---> b
a ---> g
b ---> c
c ---> d
d ---> e
c ---> f
z ---> y
y ---> x
x ---> w```

The output would be following forest.

```-->a
|-->b
|   |-->c
|   |   |-->d
|   |   |   |-->e
|   |   |-->f
|-->g

-->z
|-->y
|   |-->x
|   |   |-->w
```

You can assume that given links can form a tree or forest of trees only, and there are no duplicates among links.

Solution: The idea is to maintain two arrays, one array for tree nodes and other for trees themselves (we call this array forest). An element of the node array contains the TreeNode object that corresponds to respective character. An element of the forest array contains Tree object that corresponds to respective root of tree.

It should be obvious that the crucial part is creating the forest here, once it is created, printing it out in required format is straightforward. To create the forest, following procedure is used –

```Do following for each input link,
1. If start of link is not present in node array
Create TreeNode objects for start character
Add entries of start in both arrays.
2. If end of link is not present in node array
Create TreeNode objects for start character
Add entry of end in node array.
3. If end of link is present in node array.
If end of link is present in forest array, then remove it
from there.
4. Add an edge (in tree) between start and end nodes of link.
```

It should be clear that this procedure runs in linear time in number of nodes as well as of links – it makes only one pass over the links. It also requires linear space in terms of alphabet size.

Following is Java implementation of above algorithm. In the following implementation characters are assumed to be only lower case characters from ‘a’ to ‘z’.

`// Java program to create a custom tree from a given set of links.`
`  `
`// The main class that represents tree and has main method`
`public` `class` `Tree {`
`    `
`    ``private` `TreeNode root;`
`  `
`    ``/* Returns an array of trees from links input. Links are assumed to `
`       ``be Strings of the form "<s> <e>" where <s> and <e> are starting`
`       ``and ending points for the link. The returned array is of size 26`
`       ``and has non-null values at indexes corresponding to roots of trees`
`       ``in output */`
`    ``public` `Tree[] buildFromLinks(String [] links) {`
`          `
`        ``// Create two arrays for nodes and forest`
`        ``TreeNode[] nodes = ``new` `TreeNode[``26``];  `
`        ``Tree[] forest = ``new` `Tree[``26``];          `
`  `
`        ``// Process each link `
`        ``for` `(String link : links) {`
`              `
`            ``// Find the two ends of current link`
`            ``String[] ends = link.split(``" "``);`
`            ``int` `start = (``int``) (ends[``0``].charAt(``0``) - ``'a'``); ``// Start node`
`            ``int` `end   = (``int``) (ends[``1``].charAt(``0``) - ``'a'``); ``// End node             `
`                        `
`            ``// If start of link not seen before, add it two both arrays`
`            ``if` `(nodes[start] == ``null``) `
`            ``{                `
`                ``nodes[start] = ``new` `TreeNode((``char``) (start + ``'a'``));   `
`                `
`                ``// Note that it may be removed later when this character is`
`                ``// last character of a link. For example, let we first see`
`                ``// a--->b, then c--->a.  We first add 'a' to array of trees`
`                ``// and when we see link c--->a, we remove it from trees array.`
`                ``forest[start] = ``new` `Tree(nodes[start]);                                            `
`            ``} `
`             `
`            ``// If end of link is not seen before, add it to the nodes array`
`            ``if` `(nodes[end] == ``null``)                             `
`                ``nodes[end] = ``new` `TreeNode((``char``) (end + ``'a'``));                                 `
`            `
`            ``// If end of link is seen before, remove it from forest if `
`            ``// it exists there.`
`            ``else` `forest[end] = ``null``; `
` `
`            ``// Establish Parent-Child Relationship between Start and End`
`            ``nodes[start].addChild(nodes[end], end);`
`        ``}        `
`        ``return` `forest;`
`    ``}`
`  `
`    ``// Constructor `
`    ``public` `Tree(TreeNode root) { ``this``.root = root;  }  `
`   `
`    ``public` `static` `void` `printForest(String[] links)`
`    ``{`
`        ``Tree t = ``new` `Tree(``new` `TreeNode(``'\0'``));`
`        ``for` `(Tree t1 : t.buildFromLinks(links)) {`
`           ``if` `(t1 != ``null``)  `
`           ``{  `
`              ``t1.root.printTreeIdented(``""``);`
`              ``System.out.println(``""``);`
`           ``}  `
`        ``}`
`    ``}        `
`  `
`    ``// Driver method to test`
`    ``public` `static` `void` `main(String[] args) {`
`        ``String [] links1 = {``"a b"``, ``"b c"``, ``"b d"``, ``"a e"``};`
`        ``System.out.println(``"------------ Forest 1 ----------------"``);`
`        ``printForest(links1);       `
`        `
`        ``String [] links2 = {``"a b"``, ``"a g"``, ``"b c"``, ``"c d"``, ``"d e"``, ``"c f"``,`
`                            ``"z y"``, ``"y x"``, ``"x w"``};`
`        ``System.out.println(``"------------ Forest 2 ----------------"``);`
`        ``printForest(links2);      `
`    ``}`
`}`
`// Class to represent a tree node`
`class` `TreeNode {    `
`    ``TreeNode []children;`
`    ``char` `c;`
`    `
`    ``// Adds a child 'n' to this node`
`    ``public` `void` `addChild(TreeNode n, ``int` `index) { ``this``.children[index] = n;}  `
`    `
`    ``// Constructor`
`    ``public` `TreeNode(``char` `c) { ``this``.c = c;  ``this``.children = ``new` `TreeNode[``26``];}`
`    `
`    ``// Recursive method to print indented tree rooted with this node.`
`    ``public` `void` `printTreeIdented(String indent) {        `
`            ``System.out.println(indent + ``"-->"` `+ c);`
`            ``for` `(TreeNode child : children) {`
`              ``if` `(child != ``null``)  `
`                ``child.printTreeIdented(indent + ``"   |"``);`
`            ``}        `
`    ``}    `
`}`

Output:

```------------ Forest 1 ----------------
-->a
|-->b
|   |-->c
|   |-->d
|-->e

------------ Forest 2 ----------------
-->a
|-->b
|   |-->c
|   |   |-->d
|   |   |   |-->e
|   |   |-->f
|-->g

-->z
|-->y
|   |-->x
|   |   |-->w```

Exercise:
In the above implementation, endpoints of input links are assumed to be from set of only 26 characters. Extend the implementation where endpoints are strings of any length.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Iterative Method to find Height of Binary Tree

There are two conventions to define height of Binary Tree
1) Number of nodes on longest path from root to the deepest node.
2) Number of edges on longest path from root to the deepest node.

In this post, the first convention is followed. For example, height of the below tree is 3.

How to find height without recursion? We can use level order traversal to find height without recursion. The idea is to traverse level by level. Whenever move down to a level, increment height by 1 (height is initialized as 0). Count number of nodes at each level, stop traversing when count of nodes at next level is 0.
Following is detailed algorithm to find level order traversal using queue.

```Create a queue.
Push root into the queue.
height = 0
Loop
nodeCount = size of queue

// If number of nodes at this level is 0, return height
if nodeCount is 0
return Height;
else
increase Height

// Remove nodes of this level and add nodes of
// next level
while (nodeCount > 0)
pop node from front
push its children to queue
decrease nodeCount
// At this point, queue has nodes of next level```

Following is the implementation of above algorithm.

`/* Program to find height of the tree by Iterative Method */`
`#include <iostream>`
`#include <queue>`
`using` `namespace` `std;`
`// A Binary Tree Node`
`struct` `node`
`{`
`    ``struct` `node *left;`
`    ``int` `data;`
`    ``struct` `node *right;`
`};`
`// Iterative method to find height of Bianry Tree`
`int` `treeHeight(node *root)`
`{`
`    ``// Base Case`
`    ``if` `(root == NULL)`
`        ``return` `0;`
`    ``// Create an empty queue for level order tarversal`
`    ``queue<node *> q;`
`    ``// Enqueue Root and initialize height`
`    ``q.push(root);`
`    ``int` `height = 0;`
`    ``while` `(1)`
`    ``{`
`        ``// nodeCount (queue size) indicates number of nodes`
`        ``// at current lelvel.`
`        ``int` `nodeCount = q.size();`
`        ``if` `(nodeCount == 0)`
`            ``return` `height;`
`        ``height++;`
`        ``// Dequeue all nodes of current level and Enqueue all`
`        ``// nodes of next level`
`        ``while` `(nodeCount > 0)`
`        ``{`
`            ``node *node = q.front();`
`            ``q.pop();`
`            ``if` `(node->left != NULL)`
`                ``q.push(node->left);`
`            ``if` `(node->right != NULL)`
`                ``q.push(node->right);`
`            ``nodeCount--;`
`        ``}`
`    ``}`
`}`
`// 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);`
`    ``cout << ``"Height of tree is "` `<< treeHeight(root);`
`    ``return` `0;`
`}`

Output:

`Height of tree is 3`

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

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Minimum time required to rot all oranges

Given a matrix of dimension m*n where each cell in the matrix can have values 0, 1 or 2 which has the following meaning:

```0: Empty cell

1: Cells have fresh oranges

2: Cells have rotten oranges```

So we have to determine what is the minimum time required so that all the oranges become rotten. A rotten orange at index [i,j] can rot other fresh orange at indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right). If it is impossible to rot every orange then simply return -1.

Examples:

```Input:  arr[][C] = { {2, 1, 0, 2, 1},
{1, 0, 1, 2, 1},
{1, 0, 0, 2, 1}};
Output:
All oranges can become rotten in 2 time frames.

Input:  arr[][C] = { {2, 1, 0, 2, 1},
{0, 0, 1, 2, 1},
{1, 0, 0, 2, 1}};
Output:
All oranges cannot be rotten.

```

The idea is to user Breadth First Search. Below is algorithm.

```1) Create an empty Q.
2) Find all rotten oranges and enqueue them to Q.  Also enqueue
a delimiter to indicate beginning of next time frame.
3) While Q is not empty do following
3.a) While delimiter in Q is not reached
(i) Dequeue an orange from queue, rot all adjacent oranges.
While rotting the adjacents, make sure that time frame
is incremented only once. And time frame is not icnremented
if there are no adjacent oranges.
3.b) Dequeue the old delimiter and enqueue a new delimiter. The
oranges rotten in previous time frame lie between the two
delimiters.```

Below is implementation of the above idea.

`// C++ program to find minimum time required to make all`
`// oranges rotten`
`#include<bits/stdc++.h>`
`#define R 3`
`#define C 5`
`using` `namespace` `std;`
`// function to check whether a cell is valid / invalid`
`bool` `isvalid(``int` `i, ``int` `j)`
`{`
`    ``return` `(i >= 0 && j >= 0 && i < R && j < C);`
`}`
`// structure for storing coordinates of the cell`
`struct` `ele {`
`    ``int` `x, y;`
`};`
`// Function to check whether the cell is delimiter`
`// which is (-1, -1)`
`bool` `isdelim(ele temp)`
`{`
`    ``return` `(temp.x == -1 && temp.y == -1);`
`}`
`// Function to check whether there is still a fresh`
`// orange remaining`
`bool` `checkall(``int` `arr[][C])`
`{`
`    ``for` `(``int` `i=0; i<R; i++)`
`       ``for` `(``int` `j=0; j<C; j++)`
`          ``if` `(arr[i][j] == 1)`
`             ``return` `true``;`
`    ``return` `false``;`
`}`
`// This function finds if it is possible to rot all oranges or not.`
`// If possible, then it returns minimum time required to rot all,`
`// otherwise returns -1`
`int` `rotOranges(``int` `arr[][C])`
`{`
`    ``// Create a queue of cells`
`    ``queue<ele> Q;`
`    ``ele temp;`
`    ``int` `ans = 0;`
`    ``// Store all the cells having rotten orange in first time frame`
`    ``for` `(``int` `i=0; i<R; i++)`
`    ``{`
`       ``for` `(``int` `j=0; j<C; j++)`
`       ``{`
`            ``if` `(arr[i][j] == 2)`
`            ``{`
`                ``temp.x = i;`
`                ``temp.y = j;`
`                ``Q.push(temp);`
`            ``}`
`        ``}`
`    ``}`
`    ``// Separate these rotten oranges from the oranges which will rotten`
`    ``// due the oranges in first time frame using delimiter which is (-1, -1)`
`    ``temp.x = -1;`
`    ``temp.y = -1;`
`    ``Q.push(temp);`
`    ``// Process the grid while there are rotten oranges in the Queue`
`    ``while` `(!Q.empty())`
`    ``{`
`        ``// This flag is used to determine whether even a single fresh`
`        ``// orange gets rotten due to rotten oranges in current time`
`        ``// frame so we can increase the count of the required time.`
`        ``bool` `flag = ``false``;`
`        ``// Process all the rotten oranges in current time frame.`
`        ``while` `(!isdelim(Q.front()))`
`        ``{`
`            ``temp = Q.front();`
`            ``// Check right adjacent cell that if it can be rotten`
`            ``if` `(isvalid(temp.x+1, temp.y) && arr[temp.x+1][temp.y] == 1)`
`            ``{`
`                ``// if this is the first orange to get rotten, increase`
`                ``// count and set the flag.`
`                ``if` `(!flag) ans++, flag = ``true``;`
`                ``// Make the orange rotten`
`                ``arr[temp.x+1][temp.y] = 2;`
`                ``// push the adjacent orange to Queue`
`                ``temp.x++;`
`                ``Q.push(temp);`
`                ``temp.x--; ``// Move back to current cell`
`            ``}`
`            ``// Check left adjacent cell that if it can be rotten`
`            ``if` `(isvalid(temp.x-1, temp.y) && arr[temp.x-1][temp.y] == 1) {`
`                ``if` `(!flag) ans++, flag = ``true``;`
`                ``arr[temp.x-1][temp.y] = 2;`
`                ``temp.x--;`
`                ``Q.push(temp); ``// push this cell to Queue`
`                ``temp.x++;`
`            ``}`
`            ``// Check top adjacent cell that if it can be rotten`
`            ``if` `(isvalid(temp.x, temp.y+1) && arr[temp.x][temp.y+1] == 1) {`
`                ``if` `(!flag) ans++, flag = ``true``;`
`                ``arr[temp.x][temp.y+1] = 2;`
`                ``temp.y++;`
`                ``Q.push(temp); ``// Push this cell to Queue`
`                ``temp.y--;`
`            ``}`
`            ``// Check bottom adjacent cell if it can be rotten`
`            ``if` `(isvalid(temp.x, temp.y-1) && arr[temp.x][temp.y-1] == 1) {`
`                ``if` `(!flag) ans++, flag = ``true``;`
`                ``arr[temp.x][temp.y-1] = 2;`
`                ``temp.y--;`
`                ``Q.push(temp); ``// push this cell to Queue`
`            ``}`
`            ``Q.pop();`
`        ``}`
`        ``// Pop the delimiter`
`        ``Q.pop();`
`        ``// If oranges were rotten in current frame than separate the`
`        ``// rotten oranges using delimiter for the next frame for processing.`
`        ``if` `(!Q.empty()) {`
`            ``temp.x = -1;`
`            ``temp.y = -1;`
`            ``Q.push(temp);`
`        ``}`
`        ``// If Queue was empty than no rotten oranges left to process so exit`
`    ``}`
`    ``// Return -1 if all arranges could not rot, otherwise -1.`
`    ``return` `(checkall(arr))? -1: ans;`
`}`
`// Drive program`
`int` `main()`
`{`
`    ``int` `arr[][C] = { {2, 1, 0, 2, 1},`
`                     ``{1, 0, 1, 2, 1},`
`                     ``{1, 0, 0, 2, 1}};`
`    ``int` `ans = rotOranges(arr);`
`    ``if` `(ans == -1)`
`        ``cout << ``"All oranges cannot rotn"``;`
`    ``else`
`         ``cout << ``"Time required for all oranges to rot => "` `<< ans << endl;`
`    ``return` `0;`
`}`

Output:

```Time required for all oranges to rot => 2

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## An Interesting Method to Generate Binary Numbers from 1 to n

Given a number n, write a function that generates and prints all binary numbers with decimal values from 1 to n.

Examples:

```Input: n = 2
Output: 1, 10

Input: n = 5
Output: 1, 10, 11, 100, 101```

A simple method is to run a loop from 1 to n, call decimal to binary inside the loop.
1) Create an empty queue of strings
2) Enqueue the first binary number “1” to queue.
3) Now run a loop for generating and printing n binary numbers.
……a) Dequeue and Print the front of queue.
……b) Append “0” at the end of front item and enqueue it.
……c) Append “1” at the end of front item and enqueue it.

Following is implementation of above algorithm.

`// C++ program to generate binary numbers from 1 to n`
`#include <iostream>`
`#include <queue>`
`using` `namespace` `std;`
`// This function uses queue data structure to print binary numbers`
`void` `generatePrintBinary(``int` `n)`
`{`
`    ``// Create an empty queue of strings`
`    ``queue<string> q;`
`    ``// Enqueue the first binary number`
`    ``q.push(``"1"``);`
`    ``// This loops is like BFS of a tree with 1 as root`
`    ``// 0 as left child and 1 as right child and so on`
`    ``while` `(n--)`
`    ``{`
`        ``// print the front of queue`
`        ``string s1 = q.front();`
`        ``q.pop();`
`        ``cout << s1 << ``"\n"``;`
`        ``string s2 = s1;  ``// Store s1 before changing it`
`  `
`        ``// Append "0" to s1 and enqueue it`
`        ``q.push(s1.append(``"0"``));`
`        ``// Append "1" to s2 and enqueue it. Note that s2 contains`
`        ``// the previous front`
`        ``q.push(s2.append(``"1"``));`
`    ``}`
`}`
`// Driver program to test above function`
`int` `main()`
`{`
`    ``int` `n = 10;`
`    ``generatePrintBinary(n);`
`    ``return` `0;`
}

Output:

```1
10
11
100
101
110
111
1000
1001
1010

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Find the first circular tour that visits all petrol pumps

Suppose there is a circle. There are n petrol pumps on that circle. You are given two sets of data.

1. The amount of petrol that every petrol pump has.
2. Distance from that petrol pump to the next petrol pump.

Calculate the first point from where a truck will be able to complete the circle (The truck will stop at each petrol pump and it has infinite capacity). Expected time complexity is O(n). Assume for 1 litre petrol, the truck can go 1 unit of distance.

For example, let there be 4 petrol pumps with amount of petrol and distance to next petrol pump value pairs as {4, 6}, {6, 5}, {7, 3} and {4, 5}. The first point from where truck can make a circular tour is 2nd petrol pump. Output should be “start = 1” (index of 2nd petrol pump).

Simple Solution is to consider every petrol pumps as starting point and see if there is a possible tour. If we find a starting point with feasible solution, we return that starting point. The worst case time complexity of this solution is O(n^2).

We can use a Queue to store the current tour. We first enqueue first petrol pump to the queue, we keep enqueueing petrol pumps till we either complete the tour, or current amount of petrol becomes negative. If the amount becomes negative, then we keep dequeueing petrol pumps till the current amount becomes positive or queue becomes empty.

Instead of creating a separate queue, we use the given array itself as queue. We maintain two index variables start and end that represent rear and front of queue.

`// C program to find circular tour for a truck`
`#include <stdio.h>`
`// A petrol pump has petrol and distance to next petrol pump`
`struct` `petrolPump`
`{`
`  ``int` `petrol;`
`  ``int` `distance;`
`};`
`// The function returns starting point if there is a possible solution,`
`// otherwise returns -1`
`int` `printTour(``struct` `petrolPump arr[], ``int` `n)`
`{`
`    ``// Consider first petrol pump as a starting point`
`    ``int` `start = 0;`
`    ``int` `end =  1;`
`    ``int` `curr_petrol = arr[start].petrol - arr[start].distance;`
`    ``/* Run a loop while all petrol pumps are not visited.`
`      ``And we have reached first petrol pump again with 0 or more petrol */`
`    ``while` `(end != start || curr_petrol < 0)`
`    ``{`
`        ``// If curremt amount of petrol in truck becomes less than 0, then`
`        ``// remove the starting petrol pump from tour`
`        ``while` `(curr_petrol < 0 && start != end)`
`        ``{`
`            ``// Remove starting petrol pump. Change start`
`            ``curr_petrol -= arr[start].petrol - arr[start].distance;`
`            ``start = (start + 1)%n;`
`            ``// If 0 is being considered as start again, then there is no`
`            ``// possible solution`
`            ``if` `(start == 0)`
`               ``return` `-1;`
`        ``}`
`        ``// Add a petrol pump to current tour`
`        ``curr_petrol += arr[end].petrol - arr[end].distance;`
`        ``end = (end + 1)%n;`
`    ``}`
`    ``// Return starting point`
`    ``return` `start;`
`}`
`// Driver program to test above functions`
`int` `main()`
`{`
`    ``struct` `petrolPump arr[] = {{6, 4}, {3, 6}, {7, 3}};`
`    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]);`
`    ``int` `start = printTour(arr, n);`
`    ``(start == -1)? ``printf``(``"No solution"``): ``printf``(``"Start = %d"``, start);`
`    ``return` `0;`
`}`

Output:

`start = 2`

Time Complexity: Seems to be more than linear at first look. If we consider the items between start and end as part of a circular queue, we can observe that every item is enqueued at most two times to the queue. The total number of operations is proportional to total number of enqueue operations. Therefore the time complexity is O(n).

Auxiliary Space: O(1)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Implement Queue using Stacks

We are given a stack data structure with push and pop operations, the task is to implement a queue using instances of stack data structure and operations on them.

A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways:

Method 1 (By making enQueue operation costly) This method makes sure that oldest entered element is always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.

```enQueue(q, x)
1) While stack1 is not empty, push everything from satck1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.

dnQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it
```

Method 2 (By making deQueue operation costly)In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.

```enQueue(q,  x)
1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.
```

Method 2 is definitely better than method 1.
Method 1 moves all the elements twice in enQueue operation, while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 empty.
Implementation of method 2:

`/* Program to implement a queue using two stacks */`
`#include<stdio.h>`
`#include<stdlib.h>`
`/* structure of a stack node */`
`struct` `sNode`
`{`
`    ``int` `data;`
`    ``struct` `sNode *next;`
`};`
`/* Function to push an item to stack*/`
`void` `push(``struct` `sNode** top_ref, ``int` `new_data);`
`/* Function to pop an item from stack*/`
`int` `pop(``struct` `sNode** top_ref);`
`/* structure of queue having two stacks */`
`struct` `queue`
`{`
`    ``struct` `sNode *stack1;`
`    ``struct` `sNode *stack2;`
`};`
`/* Function to enqueue an item to queue */`
`void` `enQueue(``struct` `queue *q, ``int` `x)`
`{`
`    ``push(&q->stack1, x);`
`}`
`/* Function to dequeue an item from queue */`
`int` `deQueue(``struct` `queue *q)`
`{`
`    ``int` `x;`
`    ``/* If both stacks are empty then error */`
`    ``if``(q->stack1 == NULL && q->stack2 == NULL)`
`    ``{`
`        ``printf``(``"Q is empty"``);`
`        ``getchar``();`
`        ``exit``(0);`
`    ``}`
`/* Move elements from satck1 to stack 2 only if`
`stack2 is empty */`
`if``(q->stack2 == NULL)`
`{`
`    ``while``(q->stack1 != NULL)`
`    ``{`
`        ``x = pop(&q->stack1);`
`        ``push(&q->stack2, x);`
`        `
`    ``}`
`}`
`x = pop(&q->stack2);`
`return` `x;`
`}`
`/* Function to push an item to stack*/`
`void` `push(``struct` `sNode** top_ref, ``int` `new_data)`
`{`
`    ``/* allocate node */`
`    ``struct` `sNode* new_node =`
`        ``(``struct` `sNode*) ``malloc``(``sizeof``(``struct` `sNode));`
`        ``if``(new_node == NULL)`
`        ``{`
`            ``printf``(``"Stack overflow \n"``);`
`            ``getchar``();`
`            ``exit``(0);`
`            `
`        ``}`
`/* put in the data */`
`new_node->data = new_data;`
`/* link the old list off the new node */`
`new_node->next = (*top_ref);`
`/* move the head to point to the new node */`
`(*top_ref) = new_node;`
`}`
`/* Function to pop an item from stack*/`
`int` `pop(``struct` `sNode** top_ref)`
`{`
`    ``int` `res;`
`    ``struct` `sNode *top;`
`    `
`    ``/*If stack is empty then error */`
`    ``if``(*top_ref == NULL)`
`    ``{`
`        ``printf``(``"Stack overflow \n"``);`
`        ``getchar``();`
`        ``exit``(0);`
`        `
`    ``}`
`    ``else`
`    ``{`
`        ``top = *top_ref;`
`        ``res = top->data;`
`        ``*top_ref = top->next;`
`        ``free``(top);`
`        ``return` `res;`
`        `
`    ``}`
`}`
`/* Driver function to test anove functions */`
`int` `main()`
`{`
`    ``/* Create a queue with items 1 2 3*/`
`    ``struct` `queue *q = (``struct` `queue*)``malloc``(``sizeof``(``struct` `queue));`
`    ``q->stack1 = NULL;`
`    ``q->stack2 = NULL;`
`    ``enQueue(q, 1);`
`    ``enQueue(q, 2);`
`    ``enQueue(q, 3);`
`    `
`    ``/* Dequeue items */`
`    ``printf``(``"%d "``, deQueue(q));`
`    ``printf``(``"%d "``, deQueue(q));`
`    ``printf``(``"%d "``, deQueue(q));`
`getchar``();`
`}`

Output:

`1 2 3`

Queue can also be implemented using one user stack and one Function Call Stack. Below is modified Method 2 where recursion (or Function Call Stack) is used to implement queue using only one user defined stack.

```enQueue(x)
1) Push x to stack1.

deQueue:
1) If stack1 is empty then error.
2) If stack1 has only one element then return it.
3) Recursively pop everything from the stack1, store the popped item
in a variable res,  push the res back to stack1 and return res
```

The step 3 makes sure that the last popped item is always returned and since the recursion stops when there is only one item in stack1 (step 2), we get the last element of stack1 in dequeue() and all other items are pushed back in step

3. Implementation of method 2 using Function Call Stack:

`/* Program to implement a queue using one user defined stack `
`and one Function Call Stack */`
`#include<stdio.h>`
`#include<stdlib.h>`
`/* structure of a stack node */`
`struct` `sNode`
`{`
`    ``int` `data;`
`    ``struct` `sNode *next;`
`};`
`/* structure of queue having two stacks */`
`struct` `queue`
`{`
`    ``struct` `sNode *stack1;`
`};`
`/* Function to push an item to stack*/`
`void` `push(``struct` `sNode** top_ref, ``int` `new_data);`
`/* Function to pop an item from stack*/`
`int` `pop(``struct` `sNode** top_ref);`
`/* Function to enqueue an item to queue */`
`void` `enQueue(``struct` `queue *q, ``int` `x)`
`{`
`    ``push(&q->stack1, x);`
`}`
`/* Function to dequeue an item from queue */`
`int` `deQueue(``struct` `queue *q)`
`{`
`    ``int` `x, res;`
`    `
`    ``/* If both stacks are empty then error */`
`    ``if``(q->stack1 == NULL)`
`    ``{`
`        ``printf``(``"Q is empty"``);`
`        ``getchar``();`
`        ``exit``(0);`
`        `
`    ``}`
`    ``else` `if``(q->stack1->next == NULL)`
`    ``{`
`        ``return` `pop(&q->stack1);`
`        `
`    ``}`
`    ``else`
`    ``{`
`        ``/* pop an item from the stack1 */`
`        ``x = pop(&q->stack1);`
`        ``/* store the last dequeued item */`
`        ``res = deQueue(q);`
`        `
`        ``/* push everything back to stack1 */`
`        ``push(&q->stack1, x);`
`        ``return` `res;`
`        `
`    ``}`
`}`
`/* Function to push an item to stack*/`
`void` `push(``struct` `sNode** top_ref, ``int` `new_data)`
`{`
`    ``/* allocate node */`
`    ``struct` `sNode* new_node =`
`           ``(``struct` `sNode*) ``malloc``(``sizeof``(``struct` `sNode));`
`           `
`    ``if``(new_node == NULL)`
`    ``{`
`        ``printf``(``"Stack overflow \n"``);`
`        ``getchar``();`
`        ``exit``(0);`
`        `
`    ``}`
`/* put in the data */`
`new_node->data = new_data;`
`/* link the old list off the new node */`
`new_node->next = (*top_ref);`
`/* move the head to point to the new node */`
`(*top_ref) = new_node;`
`}`
`/* Function to pop an item from stack*/`
`int` `pop(``struct` `sNode** top_ref)`
`{`
`    ``int` `res;`
`    ``struct` `sNode *top;`
`    `
`    ``/*If stack is empty then error */`
`    ``if``(*top_ref == NULL)`
`    ``{`
`        ``printf``(``"Stack overflow \n"``);`
`        ``getchar``();`
`        ``exit``(0);`
`        `
`    ``}`
`    ``else`
`    ``{`
`    ``top = *top_ref;`
`    ``res = top->data;`
`    ``*top_ref = top->next;`
`    ``free``(top);`
`    ``return` `res;`
`    ``}`
`}`
`/* Driver function to test above functions */`
`int` `main()`
`{`
`    ``/* Create a queue with items 1 2 3*/`
`    ``struct` `queue *q = (``struct` `queue*)``malloc``(``sizeof``(``struct` `queue));`
`    ``q->stack1 = NULL;`
`    `
`    ``enQueue(q, 1);`
`    ``enQueue(q, 2);`
`    ``enQueue(q, 3);`
`    `
`    ``/* Dequeue items */`
`    ``printf``(``"%d "``, deQueue(q));`
`    ``printf``(``"%d "``, deQueue(q));`
`    ``printf``(``"%d "``, deQueue(q));`
`    `
`getchar``();`
`}`

Output:

```1 2 3

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at