Table of Contents
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
- 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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// 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; } |
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
- We use a queue to traverse each level of the tree.
- The
levelcounter 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 :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Iterative Solution int getLevelUsingQueue(TreeNode root, int data) { if (root == null) return 0; Queue<TreeNode> 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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
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<TreeNode> 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; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
=====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.
Hi,
Following your blog and its pretty good and clear. Thanks for building this up.