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.

• GFG

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. {: .prompt-tip }

• 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.

• GFG

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. {: .prompt-tip }

• 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.

• GFG

Calculate the height of the left or the right subtree {: .prompt-tip }

• 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));
    }
};