Find the Deepest Node in a Binary Tree | A Java program to find value of the deepest node in a given binary tree ; A tree node with constructor ; constructor ; Funtion to return the deepest node ; Creating a Queue ; Iterates untill queue become empty ; Driver code
import java . util . * ; public class Node { int data ; Node left , right ; Node ( int key ) { data = key ; left = null ; right = null ; } } ; class Gfg { public static Node deepestNode ( Node root ) { Node tmp = null ; if ( root == null ) return null ; Queue < Node > q = new LinkedList < Node > ( ) ; q . offer ( root ) ; while ( ! q . isEmpty ( ) ) { tmp = q . poll ( ) ; if ( tmp . left != null ) q . offer ( tmp . left ) ; if ( tmp . right != null ) q . offer ( tmp . right ) ; } return tmp ; } public static void main ( String [ ] args ) { Node root = new Node ( 1 ) ; root . left = new Node ( 2 ) ; root . right = new Node ( 3 ) ; root . left . left = new Node ( 4 ) ; root . right . left = new Node ( 5 ) ; root . right . right = new Node ( 6 ) ; root . right . left . right = new Node ( 7 ) ; root . right . right . right = new Node ( 8 ) ; root . right . left . right . left = new Node ( 9 ) ; Node deepNode = deepestNode ( root ) ; System . out . println ( deepNode . data ) ; } }