Get Level of A Node in Binary Tree in Java

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

1. Overview

In this article, we will explore how to get the level of node in a binary tree in Java using recursive and iterative solutions.

2. Introduction to Problem Statement

We will search for a node in a binary tree. The root will be at level 1. If we do not find the key in the binary tree, its level will be 0.

Given a binary tree as below:



Our goal is to find an efficient method to find level of node in binary tree. The level of node 30 would be 3 (40-20-30).

3. Implementation

There can be two solutions for it:

  • Recursive
  • Iterative

3.1 Recursive

Steps for getting level of node in binary tree:
  • If the node is null, then return 0.
  • If the node’s data is equal to the key, then return the level.
  • Recursively search key in the left subtree.
  • If not found, then search in the right subtree.

Code for recursion will be:

Time Complexity: O(n), where n is the number of nodes, as it visits each node exactly once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.

3.2 Iterative

Iterative solution will be similar to level order traversal.

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

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:


Here is a complete Java program to find the level of a node in a binary tree:
Run the above program, and you will get the following output:

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:

Please go through java interview programs for more such programs.

Was this post helpful?

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *