Priyanshu Tiwari
by Priyanshu Tiwari
2 min read

Categories

Tags

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