Home 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));
    }
};
This post is licensed under CC BY 4.0 by the author.

Atcoder Contests 2022

BST | 450 DSA | Love Babbar