Level of a node in a Tree

You are given a non empty binary tree and a key value, you need to return the level of the node with the given key value. In order to solve this problem, assume that the level of the root node is 1 and only one node with the given key exists in the tree.

Consider the tree above. The node with the key value 14 has a level 3.

Algorithm

  1. We do a simple BFS or levelOrder traversal of the tree.
  2. We maintain a queue and initialize the queue by inserting the root node. While the queue is not empty, do the following.
    Compute the size of the queue. Run a FOR loop upto the size calculated, and each time pop a node from the queue, mark its level, insert its child nodes into the queue. If the popped node has its value equal to the given key value, then return the level. Else, after the end of the FOR loop, increase the value of the level by 1 and continue.

For a better understanding, take a look at the code.

#include <bits/stdc++.h>

using namespace std;

struct Node{
  Node* left;
  Node* right;
  int data;
};

Node* createNode(int key){
    Node* temp = new Node();
    temp->data = key;
    temp->right = nullptr;
    temp->left = nullptr;
    return temp;
}

Node* root = nullptr;

Node* insertNode(Node* node, int key){
    Node* temp = createNode(key);
    if(root == nullptr){
        root = temp;
        return root;
    }
    if(node == nullptr){
        return temp;   
    }
    
    if(key < node->data){
        node->left = insertNode(node->left, key);
    }else if(key > node->data){
        node->right = insertNode(node->right, key);
    }
    return node;
}

int getLevel(Node* root, int key){
    queue<Node*> q;
    q.push(root);
    int level = 1;
    while(!q.empty()){
        int n = q.size();
        for(int i = 1; i <= n; i++){
            Node* temp = q.front();
            q.pop();
            if(temp->data == key){
                return level;
            }
            if(temp->left){
                q.push(temp->left);
            }
            if(temp->right){
                q.push(temp->right);
            }
        }
        level+=1;
    }
    return 0;
}


void levelOrderTraversal(){
    Node* temp = root;
    queue<Node*> q;
    q.push(temp);
    while(!q.empty()){
        Node* front = q.front();
        cout<<front->data<<" ";
        q.pop();
        if(front->left != nullptr){
            q.push(front->left);
        }
        if(front->right != nullptr){
            q.push(front->right);
        }
    }
}

int main()
{
    insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 10);
    insertNode(root, 1);
    insertNode(root, 6);
    insertNode(root, 14);
    insertNode(root, 4);
    insertNode(root, 7);
    insertNode(root, 13);
    levelOrderTraversal();
    cout<<endl;
    cout<<"Level of 14 is: "<<getLevel(root, 14)<<endl;
    return 0;
}	

Also, take a look at another popular interview problem Maximum Path Sum

One comment

Leave a Reply

Your email address will not be published.