Get Level of a node in a Binary Tree

Last Updated : 21 Nov, 2022

Given a Binary Tree and a key, write a function that returns level of the key.

For example, consider the following tree. If the input key is 3, then your function should return 1. If the input key is 4, then your function should return 3. And for key which is not present in key, then your function should return 0.

The idea is to start from the root and level as 1. If the key matches with root’s data, return level. Else recursively call for left and right subtrees with level as level + 1.

C++

// C++ program to Get Level of a node in a Binary Tree
#include <bits/stdc++.h>
using namespace std;
 
/* A tree node structure */
struct node {
    int data;
    struct node* left;
    struct node* right;
};
// Helper function for getLevel(). It returns level of the
// data if data is present in tree, otherwise returns 0.
int getLevelUtil(struct node* node, int data, int level)
{
    if (node == NULL)
        return 0;
 
    if (node->data == data)
        return level;
 
    int downlevel
        = getLevelUtil(node->left, data, level + 1);
    if (downlevel != 0)
        return downlevel;
 
    downlevel = getLevelUtil(node->right, data, level + 1);
    return downlevel;
}
 
/* Returns level of given data value */
int getLevel(struct node* node, int data)
{
    return getLevelUtil(node, data, 1);
}
 
// Utility function to create a new Binary Tree node
struct node* newNode(int data)
{
    struct node* temp = new struct node;
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
 
// Driver Code
int main()
{
    struct node* root = new struct node;
    int x;
 
    // Constructing tree given in the above figure
    root = newNode(3);
    root->left = newNode(2);
    root->right = newNode(5);
    root->left->left = newNode(1);
    root->left->right = newNode(4);
 
    for (x = 1; x <= 5; x++) {
        int level = getLevel(root, x);
        if (level)
            cout << "Level of " << x << " is " << level
                 << endl;
        else
            cout << x << "is not present in tree" << endl;
    }
 
    getchar();
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

C

// C program to Get Level of a node in a Binary Tree
#include <stdio.h>
#include <stdlib.h>
 
/* A tree node structure */
typedef struct node {
    int data;
    struct node* left;
    struct node* right;
} node;
 
// Helper function for getLevel(). It returns level of the
// data if data is present in tree, otherwise returns 0.
int getLevelUtil(node* node, int data, int level)
{
    if (node == NULL)
        return 0;
 
    if (node->data == data)
        return level;
 
    int downlevel
        = getLevelUtil(node->left, data, level + 1);
    if (downlevel != 0)
        return downlevel;
 
    downlevel = getLevelUtil(node->right, data, level + 1);
    return downlevel;
}
 
/* Returns level of given data value */
int getLevel(node* node, int data)
{
    return getLevelUtil(node, data, 1);
}
 
// Utility function to create a new Binary Tree node
node* newNode(int data)
{
    node* temp = (node*)malloc(sizeof(node));
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
 
/* Driver code */
int main()
{
    node* root;
    int x;
 
    // Constructing tree given in the above figure
    root = newNode(3);
    root->left = newNode(2);
    root->right = newNode(5);
    root->left->left = newNode(1);
    root->left->right = newNode(4);
 
    for (x = 1; x <= 5; x++) {
        int level = getLevel(root, x);
        if (level)
            printf(" Level of %d is %d\n", x,
                   getLevel(root, x));
        else
            printf(" %d is not present in tree \n", x);
    }
 
    getchar();
    return 0;
}

Java

// Java program to Get Level of a node in a Binary Tree
/* A tree node structure */
class Node {
    int data;
    Node left, right;
 
    public Node(int d)
    {
        data = d;
        left = right = null;
    }
}
 
class BinaryTree {
 
    Node root;
 
    // Helper function for getLevel(). It returns level of
    // the data if data is present in tree, otherwise
    // returns 0.
    int getLevelUtil(Node node, int data, int level)
    {
        if (node == null)
            return 0;
 
        if (node.data == data)
            return level;
 
        int downlevel
            = getLevelUtil(node.left, data, level + 1);
        if (downlevel != 0)
            return downlevel;
 
        downlevel
            = getLevelUtil(node.right, data, level + 1);
        return downlevel;
    }
 
    /* Returns level of given data value */
    int getLevel(Node node, int data)
    {
        return getLevelUtil(node, data, 1);
    }
 
    /* Driver code */
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
 
        /* Constructing tree given in the above figure */
        tree.root = new Node(3);
        tree.root.left = new Node(2);
        tree.root.right = new Node(5);
        tree.root.left.left = new Node(1);
        tree.root.left.right = new Node(4);
        for (int x = 1; x <= 5; x++) {
            int level = tree.getLevel(tree.root, x);
            if (level != 0)
                System.out.println(
                    "Level of " + x + " is "
                    + tree.getLevel(tree.root, x));
            else
                System.out.println(
                    x + " is not present in tree");
        }
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Python3

# Python3 program to Get Level of a
# node in a Binary Tree
 
# Helper function that allocates a
# new node with the given data and
# None left and right pairs.
 
 
class newNode:
 
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Helper function for getLevel(). It
# returns level of the data if data is
# present in tree, otherwise returns 0
 
 
def getLevelUtil(node, data, level):
    if (node == None):
        return 0
 
    if (node.data == data):
        return level
 
    downlevel = getLevelUtil(node.left,
                             data, level + 1)
    if (downlevel != 0):
        return downlevel
 
    downlevel = getLevelUtil(node.right,
                             data, level + 1)
    return downlevel
 
# Returns level of given data value
 
 
def getLevel(node, data):
 
    return getLevelUtil(node, data, 1)
 
 
# Driver Code
if __name__ == '__main__':
 
    # Let us construct the Tree shown
    # in the above figure
    root = newNode(3)
    root.left = newNode(2)
    root.right = newNode(5)
    root.left.left = newNode(1)
    root.left.right = newNode(4)
    for x in range(1, 6):
        level = getLevel(root, x)
        if (level):
            print("Level of", x,
                  "is", getLevel(root, x))
        else:
            print(x, "is not present in tree")
 
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

C#

// C# program to Get Level of a node in a Binary Tree
using System;
 
/* A tree node structure */
public class Node {
    public int data;
    public Node left, right;
 
    public Node(int d)
    {
        data = d;
        left = right = null;
    }
}
 
public class BinaryTree {
 
    public Node root;
 
    /* Helper function for getLevel().
       It returns level of
       the data if data is present in tree,
      otherwise returns
    0.*/
    public virtual int getLevelUtil(Node node, int data,
                                    int level)
    {
        if (node == null) {
            return 0;
        }
 
        if (node.data == data) {
            return level;
        }
 
        int downlevel
            = getLevelUtil(node.left, data, level + 1);
        if (downlevel != 0) {
            return downlevel;
        }
 
        downlevel
            = getLevelUtil(node.right, data, level + 1);
        return downlevel;
    }
 
    /* Returns level of given data value */
    public virtual int getLevel(Node node, int data)
    {
        return getLevelUtil(node, data, 1);
    }
 
    /* Driver code */
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
 
        /* Constructing tree given in the above figure */
        tree.root = new Node(3);
        tree.root.left = new Node(2);
        tree.root.right = new Node(5);
        tree.root.left.left = new Node(1);
        tree.root.left.right = new Node(4);
        for (int x = 1; x <= 5; x++) {
            int level = tree.getLevel(tree.root, x);
            if (level != 0) {
                Console.WriteLine(
                    "Level of " + x + " is "
                    + tree.getLevel(tree.root, x));
            }
            else {
                Console.WriteLine(
                    x + " is not present in tree");
            }
        }
    }
}
 
// This code is contributed by Shrikant13

Javascript

<script>
 
    // Javascript program to Get Level of
    // a node in a Binary Tree
    /* A tree node structure */
     
    class Node
    {
        constructor(d) {
              this.data = d;
            this.left = null;
            this.right = null;
        }
    }
     
    let root;
  
    /* Helper function for getLevel().
       It returns level of
       the data if data is present in tree,
       otherwise returns
       0.*/
    function getLevelUtil(node, data, level)
    {
        if (node == null)
            return 0;
  
        if (node.data == data)
            return level;
  
        let downlevel
            = getLevelUtil(node.left, data, level + 1);
        if (downlevel != 0)
            return downlevel;
  
        downlevel
            = getLevelUtil(node.right, data, level + 1);
        return downlevel;
    }
  
    /* Returns level of given data value */
    function getLevel(node, data)
    {
        return getLevelUtil(node, data, 1);
    }
     
    /* Constructing tree given in the above figure */
    root = new Node(3);
    root.left = new Node(2);
    root.right = new Node(5);
    root.left.left = new Node(1);
    root.left.right = new Node(4);
    for (let x = 1; x <= 5; x++)
    {
      let level = getLevel(root, x);
      if (level != 0)
        document.write(
          "Level of " + x + " is "
          + getLevel(root, x) + "</br>");
      else
        document.write(
          x + " is not present in tree");
    }
     
</script>

Output

Level of 1 is 3
Level of 2 is 2
Level of 3 is 1
Level of 4 is 3
Level of 5 is 2

Time Complexity: O(n) where n is the number of nodes in the given Binary Tree.
Auxiliary Space: O(n)

Alternative Approach: The given problem can be solved with the help of level order traversal of given binary tree.

C++

// C++ program to print level in which X is present in
// binary tree using STL
#include <bits/stdc++.h>
using namespace std;
 
// A Binary Tree Node
struct Node {
    int data;
    struct Node *left, *right;
};
 
int printLevel(Node* root, int X)
{
    Node* node;
    // Base Case
    if (root == NULL)
        return 0;
    // Create an empty queue for level order traversal
    queue<Node*> q;
    // Create a var represent current level of tree
    int currLevel = 1;
    // Enqueue Root 
    q.push(root);
    while (q.empty() == false) {
        int size = q.size();
        while (size--) {
            node = q.front();
            if (node->data == X)
                return currLevel;
            q.pop();
            /* Enqueue left child */
            if (node->left != NULL)
                q.push(node->left);
            /*Enqueue right child */
            if (node->right != NULL)
                q.push(node->right);
        }
        currLevel++;
    }
    return 0;
}
 
// Utility function to create a new tree node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
// Driver program to test above functions
int main()
{
    // Let us create binary tree shown in above diagram
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(7);
    root->right->right = newNode(6);
 
    cout << printLevel(root, 6);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java program to print level in which X is present in
// binary tree
import java.util.LinkedList;
import java.util.Queue;
 
/* Class to represent Tree node */
class Node {
    int data;
    Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = null;
        right = null;
    }
}
 
/* Class to print Level Order Traversal */
class BinaryTree {
 
    Node root;
 
    // Given a binary tree. Print its nodes in level order
    // using array for implementing queue.
    // Create a var represent current level of tree
    public static int currLevel = 1;
    int printLevelOrder(int X)
    {
        // Create an empty queue for level order traversal
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
 
        while (!queue.isEmpty()) {
 
            // poll() removes the present head. For more
            // information on poll() visit
            // https://www.geeksforgeeks.org/queue-poll-method-in-java/
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node tempNode = queue.poll();
                if (tempNode.data == X)
                    return currLevel;
                /*Enqueue left child */
                if (tempNode.left != null)
                    queue.add(tempNode.left);
                /*Enqueue right child */
                if (tempNode.right != null)
                    queue.add(tempNode.right);
            }
            currLevel++;
        }
        return currLevel;
    }
 
    public static void main(String args[])
    {
        /* creating a binary tree and entering
            the nodes */
        BinaryTree tree_level = new BinaryTree();
        tree_level.root = new Node(1);
        tree_level.root.left = new Node(2);
        tree_level.root.right = new Node(3);
        tree_level.root.left.left = new Node(4);
        tree_level.root.left.right = new Node(5);
        tree_level.root.right.left = new Node(7);
        tree_level.root.right.right = new Node(6);
        System.out.println(
            "Level order traversal of binary tree is - "
            + tree_level.printLevelOrder(6));
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Python3

# Python3 program to print level in which X is present in
# binary tree
 
# A node structure
class Node:
    # A utility function to create a new node
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None
 
def printLevel(root, X):
    # Base Case
    if root is None:
        return 0
    # Create an empty queue
    # for level order traversal
    q = []
    #Create a var represent current level of tree
    currLevel = 1
    # Enqueue Root 
    q.append(root)
     
    while(len(q) > 0):
        size = len(q)
        for i in range(size):
            node = q.pop(0)
            if(node.data == X):
                return currLevel
            # Enqueue left child
            if node.left is not None:
                q.append(node.left)
            # Enqueue right child
            if node.right is not None:
                q.append(node.right)
        currLevel += 1
    return 0
 
# Driver Program to test above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(7)
root.right.right = Node(6)
 
print(printLevel(root, 6))
 
# This code is contributed by Abhijeet Kumar(abhijeet19403)

C#

// C# program to print level in which X is present in
// binary tree
 
using System;
using System.Collections.Generic;
 
/* Class to represent Tree node */
public class Node {
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = null;
        right = null;
    }
}
 
/* Class to print Level Order Traversal */
public class BinaryTree {
    Node root;
 
    /* Function to get the level of the node X*/
    int printLevel(int X)
    {
        Node node;
        // Base Case
        if (root == null)
            return 0;
        // Create an empty queue for level order traversal
        Queue<Node> q = new Queue<Node>();
        // Create a var represent current level of tree
        int currLevel = 1;
        // Enqueue root
        q.Enqueue(root);
        while (q.Count != 0) {
            int size = q.Count;
            while (size-- != 0) {
                node = q.Dequeue();
                if (node.data == X)
                    return currLevel;
                /*Enqueue left child */
                if (node.left != null)
                    q.Enqueue(node.left);
                /*Enqueue right child */
                if (node.right != null)
                    q.Enqueue(node.right);
            }
            currLevel++;
        }
        return 0;
    }
 
    // Driver code
    public static void Main()
    {
        /* creating a binary tree and entering
        the nodes */
        BinaryTree tree_level = new BinaryTree();
        tree_level.root = new Node(1);
        tree_level.root.left = new Node(2);
        tree_level.root.right = new Node(3);
        tree_level.root.left.left = new Node(4);
        tree_level.root.left.right = new Node(5);
        tree_level.root.right.left = new Node(7);
        tree_level.root.right.right = new Node(6);
 
        Console.WriteLine(tree_level.printLevel(6));
    }
}
 
/* This code contributed by Abhijeet Kumar(abhijeet19403) */

Javascript

// JavaScript program to print level in which X is present in
// binary tree
 
class Node
{
    constructor(d) {
        this.data = d;
        this.left = null;
        this.right = null;
    }
}
 
let root;
 
// Given a binary tree. Print its nodes in level order
// using array for implementing queue.
// Create a var represent current level of tree
let currLevel = 1;
 
function printLevelOrder(X){
    // Create an empty queue for level order traversal
    let queue = [root];
    while(queue[0]){
        let size = queue.length;
        for(let i=0;i<size;i++){
            let tempNode = queue.shift();
            if(tempNode.data==X){
                return currLevel;
            }
            /*Enqueue left child */
            if(tempNode.left){
                queue.push(tempNode.left);
            }
            /*Enqueue right child */
            if(tempNode.right){
                queue.push(tempNode.right);
            }
        }
        currLevel+=1;
    }
    return root.data;
}
 
 
/* creating a binary tree and entering
        the nodes */
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(7);
root.right.right = new Node(6);
console.log(printLevelOrder(6));
 
// This code is contributed by lokeshmvs21.

Output

Time Complexity: O(n) where n is the number of nodes in the binary tree.
Auxiliary Space: O(n) where n is the number of nodes in the binary tree.

GeeksforGeeks

Improve

Previous Article

Diameter of a Binary Tree

Find all possible binary trees with given Inorder Traversal

Similar Reads

Count nodes from all lower levels smaller than minimum valued node of current level for every level in a Binary Tree

Given a Binary Tree, the task is for each level is to print the total number of nodes from all lower levels which are less than or equal to every node present at that level. Examples: Input: Below is the given tree: 4 / \ 3 5 / \ / \ 10 2 3 1 Output: 4 3 0Explanation:Nodes in level 1 has 4 nodes as (3) in level 2 and (2, 3, 1) in level 3. Nodes in

Get level of a node in binary tree | iterative approach

Given a Binary Tree and a key, write a function that returns level of the key. For example, consider the following tree. If the input key is 3, then your function should return 1. If the input key is 4, then your function should return 3. And for key which is not present in key, then your function should return 0. Recursive approach to this problem

Minimum value to be added at each level in Binary Tree to make all level sum equal

Given a binary tree, the task is to find all minimum values greater than or equal to zero, that should be added at each level to make the sum at each level equal. Examples: Input: 1 / \ 2 3 / \ 4 5 Output: 8 4 0Explanation: Initial sum at each level is {1, 5, 9}. To make all levels sum equal minimum values to be added are {8, 4, 0}. So the final su

Print the nodes corresponding to the level value for each level of a Binary Tree

Given a Binary Tree, the task for each level L is to print the Lth node of the tree. If the Lth node is not present for any level, print -1. Note: Consider the root node to be at the level 1 of the binary tree. Examples: Input: Below is the given Tree: Output:Level 1: 1Level 2: 3 Level 3: 6Level 4: 11Explanation:For the first level, the 1st node is

Print nodes of a Binary Search Tree in Top Level Order and Reversed Bottom Level Order alternately

Given a Binary Search Tree, the task is to print the nodes of the BST in the following order: If the BST contains levels numbered from 1 to N then, the printing order is level 1, level N, level 2, level N - 1, and so on.The top-level order (1, 2, …) nodes are printed from left to right, while the bottom level order (N, N-1, ...) nodes are printed f

Modify a Binary Tree by adding a level of nodes with given value at a specified level

Given a Binary Tree consisting of N nodes and two integers K and L, the task is to add one row of nodes of value K at the Lth level, such that the orientation of the original tree remains unchanged. Examples: Input: K = 1, L = 2 Output:11 12 34 5 6 Explanation:Below is the tree after inserting node with value 1 in the K(= 2) th level. Input: K = 1,

Difference between odd level and even level leaf sum in given Binary Tree

Given a Binary Tree, the task is to find the difference of the sum of leaf nodes at the odd level and even level of the given tree. Examples: Input: Output: -12Explanation: Following are the operations performed to get the result.odd_level_sum = 0, even_level_sum = 0Level 1: No leaf node, so odd_level_sum = 0Level 2: No leaf node, so even_level_sum

Difference between sums of odd level and even level nodes of a Binary Tree

Given a Binary Tree, find the difference between the sum of nodes at odd level and the sum of nodes at even level. Consider root as level 1, left and right children of root as level 2 and so on. For example, in the following tree, sum of nodes at odd level is (5 + 1 + 4 + 8) which is 18. And sum of nodes at even level is (2 + 6 + 3 + 7 + 9) which i

Sum of decimal equivalents of binary node values in each level of a Binary Tree

Given a Binary Tree consisting of nodes with values 0 and 1 only, the task is to find the total sum of the decimal equivalents of the binary numbers formed by connecting nodes at the same level from left to right, on each level. Examples: Input: Below is the given Tree: 0 / \ 1 0 / \ / \ 0 1 1 1Output: 9Explanation: Binary number formed at level 1

Level of Each node in a Tree from source node (using BFS)

Given a tree with v vertices, find the level of each node in a tree from the source node. Examples: Input : Output : Node Level 0 0 1 1 2 1 3 2 4 2 5 2 6 2 7 3 Explanation : Input: Output : Node Level 0 0 1 1 2 1 3 2 4 2 Explanation: Approach: BFS(Breadth-First Search) is a graph traversal technique where a node and its neighbours are visited first

Article Tags :

DSA
Tree

Practice Tags :

Tree