Binary Tree | 450 DSA | Love Babbar
Post
Cancel

# Binary Tree | 450 DSA | Love Babbar

### 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)
```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 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)
```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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)
```1 2 3 4 5 6 7 class Solution{ public: int height(struct Node* node){ if(!node) return 0; return 1 + max(height(node->left), height(node->right)); } }; ```