Find the Deepest Node in a Binary Tree | A C ++ program to find value of the deepest node in a given binary tree ; A tree node with constructor ; Utility function to find height of a tree , rooted at ' root ' . ; levels : current Level Utility function to print all nodes at a given level . ; Driver program ; Calculating height of tree ; Printing the deepest node
#include <bits/stdc++.h> NEW_LINE using namespace std ; class Node { public : int data ; Node * left , * right ; Node ( int key ) { data = key ; left = NULL ; right = NULL ; } } ; int height ( Node * root ) { if ( ! root ) return 0 ; int leftHt = height ( root -> left ) ; int rightHt = height ( root -> right ) ; return max ( leftHt , rightHt ) + 1 ; } void deepestNode ( Node * root , int levels ) { if ( ! root ) return ; if ( levels == 1 ) cout << root -> data ; else if ( levels > 1 ) { deepestNode ( root -> left , levels - 1 ) ; deepestNode ( root -> right , levels - 1 ) ; } } int main ( ) { 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 ) ; int levels = height ( root ) ; deepestNode ( root , levels ) ; return 0 ; }