Deepest right leaf node in a binary tree | Iterative approach | CPP program to find deepest right leaf node of binary tree ; tree node ; returns a new tree Node ; return the deepest right leaf node of binary tree ; create a queue for level order traversal ; traverse until the queue is empty ; Since we go level by level , the last stored right leaf node is deepest one ; driver program ; construct a tree
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; } ; Node * newNode ( int data ) { Node * temp = new Node ( ) ; temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } Node * getDeepestRightLeafNode ( Node * root ) { if ( ! root ) return NULL ; queue < Node * > q ; q . push ( root ) ; Node * result = NULL ; while ( ! q . empty ( ) ) { Node * temp = q . front ( ) ; q . pop ( ) ; if ( temp -> left ) { q . push ( temp -> left ) ; } if ( temp -> right ) { q . push ( temp -> right ) ; if ( ! temp -> right -> left && ! temp -> right -> right ) result = temp -> right ; } } return result ; } int main ( ) { Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> right = newNode ( 4 ) ; root -> right -> left = newNode ( 5 ) ; root -> right -> right = newNode ( 6 ) ; root -> right -> left -> right = newNode ( 7 ) ; root -> right -> right -> right = newNode ( 8 ) ; root -> right -> left -> right -> left = newNode ( 9 ) ; root -> right -> right -> right -> right = newNode ( 10 ) ; Node * result = getDeepestRightLeafNode ( root ) ; if ( result ) cout << " Deepest ▁ Right ▁ Leaf ▁ Node ▁ : : ▁ " << result -> data << endl ; else cout << " No ▁ result , ▁ right ▁ leaf ▁ not ▁ found STRNEWLINE " ; return 0 ; }