 by Priyanshu Tiwari

## Table Of Content

### Level order traversal #

Given a binary tree, find its level order traversal. Level order traversal of a tree is breadth-first traversal for the tree.

Create a queue, insert the root node, pop the queue in a temp variable and push the left and the right child. Repeat until the queue is empty.

• Time Complexity : O(n)
• Space Complexity : O(n)
class Solution
{
public:
vector<int> levelOrder(Node* root){
queue<Node*> q;
vector<int> v;
q.push(root);
while(!q.empty()){
Node *tmp = q.front();
v.push_back(tmp->data);
if(tmp->left)
q.push(tmp->left);
if(tmp->right)
q.push(tmp->right);
q.pop();
}
return v;
}
};


### Reverse Level Order Traversal #

Given a binary tree of size N, find its reverse level order traversal. ie- the traversal must begin from the last level.

Create a queue, insert the root node, pop the queue in a temp variable and push the right and then the left child. Repeat until the queue is empty. Reverse the resultant vector.

• Time Complexity : O(n)
• Space Complexity : O(n)
vector<int> reverseLevelOrder(Node *root)
{
queue<Node*> q;
vector<int> v;
q.push(root);
while(!q.empty()){
Node *tmp = q.front();
v.push_back(tmp->data);
if(tmp->right)
q.push(tmp->right);
if(tmp->left)
q.push(tmp->left);

q.pop();
}
reverse(v.begin(), v.end());
return v;
}


### Height of Binary Tree #

Given a binary tree, find its height.

Calculate the height of the left or the right subtree

• Time Complexity : O(n)
• Space Complexity : O(n)
class Solution{
public:
int height(struct Node* node){
if(!node) return 0;
return 1 + max(height(node->left), height(node->right));
}
};