Get Level of A Node in Binary Tree in Java

There can be two solutions for it:

• Recursive
• Iterative

3.1 Recursive

• We use a queue to traverse each level of the tree.
• The level counter is incremented at the start of each new level.
• When the target node is found, the current level is returned.

Code for iteration will be :

        
// Iterative Solution
int getLevelUsingQueue(TreeNode root, int data) {
    if (root == null)
        return 0;

    Queue queue = new LinkedList<>();
    queue.add(root);
    int level = 0;

    while (!queue.isEmpty()) {
        level++;
        int size = queue.size();

        while (size-- > 0) {
            TreeNode temp = queue.poll();

            if (temp.data == data)
                return level;

            if (temp.left != null)
                queue.add(temp.left);
            if (temp.right != null)
                queue.add(temp.right);
        }
    }
    return 0;
}

Time Complexity: O(n), similar to the recursive solution.
Space Complexity: O(h), but since it’s iterative, it avoids the potential stack overflow issue.

4. Complete Java Program

Let’s say our binary tree is:

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTreeGetLevelNode {

    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }

    // Recursive Solution
    //To get level of node in a binary tree
    public static int getLevelOfNode(TreeNode root,int key,int level)
    {
        if(root==null)
            return 0;
        if(root.data==key)
            return level;

        int result=getLevelOfNode(root.left,key,level+1) ;
        if(result!=0)
        {
            // If found in left subtree , return
            return result;
        }
        result= getLevelOfNode(root.right,key,level+1);

        return result;
    }

    // Iterative Solution
    public static int getLevelUsingQueue(TreeNode root, int data) {
        if (root == null)
            return 0;

        Queue queue = new LinkedList<>();
        queue.add(root);
        int level = 0;

        while (!queue.isEmpty()) {
            level++;
            int size = queue.size();

            while (size-- > 0) {
                TreeNode temp = queue.poll();

                if (temp.data == data)
                    return level;

                if (temp.left != null)
                    queue.add(temp.left);
                if (temp.right != null)
                    queue.add(temp.right);
            }
        }
        return 0;
    }


    public static void main(String[] args)
    {
        // Creating a binary tree
        TreeNode rootNode=createBinaryTree();
        System.out.println("=====Recursive Solution=====");
        System.out.println("Node data: 70,Level: "+getLevelOfNode(rootNode, 70, 1));
        System.out.println("Node data: 100,Level: "+getLevelOfNode(rootNode, 100, 1));
        System.out.println("Node data: 60,Level: "+getLevelOfNode(rootNode, 60, 1));
        System.out.println("Node data: 40,Level: "+getLevelOfNode(rootNode, 40, 1));

        System.out.println("=====Iterative Solution=====");
        System.out.println("Node data: 70,Level: "+getLevelUsingQueue(rootNode, 70));
        System.out.println("Node data: 100,Level: "+getLevelUsingQueue(rootNode, 100));
        System.out.println("Node data: 60,Level: "+getLevelUsingQueue(rootNode, 60));
        System.out.println("Node data: 40,Level: "+getLevelUsingQueue(rootNode, 40));

    }

    public static TreeNode createBinaryTree()
    {

        TreeNode rootNode =new TreeNode(40);
        TreeNode node20=new TreeNode(20);
        TreeNode node10=new TreeNode(10);
        TreeNode node30=new TreeNode(30);
        TreeNode node60=new TreeNode(60);
        TreeNode node50=new TreeNode(50);
        TreeNode node70=new TreeNode(70);

        rootNode.left=node20;
        rootNode.right=node60;

        node20.left=node10;
        node20.right=node30;

        node60.left=node50;
        node60.right=node70;

        return rootNode;
    }
}

Run the above program, and you will get the following output:

=====Recursive Solution=====
Node data: 70,Level: 3
Node data: 100,Level: 0
Node data: 60,Level: 2
Node data: 40,Level: 1
=====Iterative Solution=====
Node data: 70,Level: 3
Node data: 100,Level: 0
Node data: 60,Level: 2
Node data: 40,Level:1

5. Conclusion

In this article, we covered finding the level of node in a binary tree. We have done traversal using two approaches: Iterative and Recursive. We also discussed the time and space complexity of the solutions.
Java Binary tree tutorial:

• Binary tree in java
• Binary tree preorder traversal
• Binary tree postorder traversal
• Binary tree inorder traversal
• Binary tree level order traversal
• Binary tree spiral order traversal
• Binary tree reverse level order traversal
• Binary tree boundary traversal
• Print leaf nodes of binary tree
• Count leaf nodes in binary tree
• get maximum element in binary tree
• Print all paths from root to leaf in binary tree
• Print vertical sum of binary tree in java
• Get level of node in binary tree in java
• Lowest common ancestor(LCA) in binary tree in java

Please go through java interview programs for more such programs.