- Given a binary tree, find out the level of input node using non recursive algorithm.
- Traverse the binary tree using breadth first search (BFS) or level order traversal algorithm.
- What is level in a binary tree?
- Level is distance or hops of node with respect to root node.
- The root node is considered to be at level 0 & immediate children of root node is at level 1 (level of root node + 1).
- Calculate the level of all the nodes in a binary tree (wrt level of its parent node).
The root node A is at level 0 and its children B and C is at level 1 (refer Fig 1)
The level of nodes in a binary tree are as follows:
No. | Binary Tree Node (s) | Level |
---|---|---|
1 | A | 0 |
2 | B, C | 1 |
3 | D, E, F, G | 2 |
4 | H, I | 3 |
- Insert root to queue.
- Insert null to the queue (delimiter to know that we have finished the current level)
- Iterate through the Queue
- Pop node from queue
- Check node is null [The delimiter added earlier]
- We are at next level and Increment the level.
- Compare the popped up node with input node [data]
- If this the node we are looking for.
- We got the level, break from the loop
- If this the node we are looking for.
- Add next level children (left and right child)
- Once we exit the loop, we will know the level of input node (if found in tree).
Let us go through the complete code, to find out the level of input node using level order traversal or breadth first search non recursive algorithm as follows:
1.) LevelOfNodeInBTree Class: LevelOfNodeInBTree is used to find the level of node using breadth first search algorithm in a binary tree.
package org.learn.Question; import java.util.LinkedList; import java.util.Queue; public class LevelOfNodeInBTree { public static void levelOfNodeInBTree(Node root, Node inputNode) { if (root == null) { System.out.println("Tree is empty"); return ; } Queue<Node> queue = new LinkedList<Node>(); queue.offer(root); //level delimiter queue.offer(null); int level = 0; boolean found = false; while (!queue.isEmpty()) { Node node = queue.poll(); //Level change if (null == node) { if (!queue.isEmpty()) { //level delimiter queue.offer(null); } level ++; } else { if( inputNode.data == node.data) { found = true; break; } if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } } if(found) { System.out.printf("Found data %d at level %d \n",inputNode.data,level); } else { System.out.printf("Node could not found in binary tree"); } return; } }
2.) Node Class: The class representing the nodes of a binary tree.
package org.learn.Question; public class Node { public int data; public Node left; public Node right; public Node(int num) { this.data = num; this.left = null; this.right = null; } public Node() { this.left = null; this.right = null; } public static Node createNode(int number) { return new Node(number); } }
3.) App Class: We are creating the binary tree in a main method & Calling LevelOfNodeInBTree class ,to find the level of input node in a binary tree using level order traversal algorithm.
package org.learn.Client; import org.learn.Question.LevelOfNodeInBTree; import org.learn.Question.Node; public class App { public static void main( String[] args ) { //root level 0 Node A = Node.createNode(100); //Level 1 Node B = Node.createNode(50); Node C = Node.createNode(150); //Level 2 Node D = Node.createNode(25); Node E = Node.createNode(75); Node F = Node.createNode(125); Node G = Node.createNode(175); //Level 3 Node H = Node.createNode(120); Node I = Node.createNode(140); //connect Level 0 and 1 A.left = B; A.right = C; //connect level 1 and level 2 B.left = D; B.right = E; C.left = F; C.right = G; //Connect level 2 and level 3 F.left = H; F.right = I; //Pass root node and input node LevelOfNodeInBTree.levelOfNodeInBTree(A,A); LevelOfNodeInBTree.levelOfNodeInBTree(A,C); LevelOfNodeInBTree.levelOfNodeInBTree(A,F); LevelOfNodeInBTree.levelOfNodeInBTree(A,H); } }
The output of main function is as follows:
Found data 100 at level 0 Found data 150 at level 1 Found data 125 at level 2 Found data 120 at level 3
Download Code–Level of node in binary tree non-recursive