Find depth of the deepest odd level leaf node | CPP program to find depth of the deepest odd level leaf node of binary tree ; tree node ; returns a new tree Node ; return max odd number depth of leaf node ; create a queue for level order traversal ; traverse until the queue is empty ; traverse for complete level ; check if the node is leaf node and level is odd if level is odd , then update result ; check for left child ; check for right child ; 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 ; } int maxOddLevelDepth ( Node * root ) { if ( ! root ) return 0 ; queue < Node * > q ; q . push ( root ) ; int result = INT_MAX ; int level = 0 ; while ( ! q . empty ( ) ) { int size = q . size ( ) ; level += 1 ; while ( size > 0 ) { Node * temp = q . front ( ) ; q . pop ( ) ; if ( ! temp -> left && ! temp -> right && ( level % 2 != 0 ) ) { result = level ; } if ( temp -> left ) { q . push ( temp -> left ) ; } if ( temp -> right ) { q . push ( temp -> right ) ; } size -= 1 ; } } return result ; } int main ( ) { Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = 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 ) ; root -> right -> right -> right -> right -> left = newNode ( 11 ) ; int result = maxOddLevelDepth ( root ) ; if ( result == INT_MAX ) cout << " No ▁ leaf ▁ node ▁ at ▁ odd ▁ level STRNEWLINE " ; else cout << result ; cout << " ▁ is ▁ the ▁ required ▁ depth ▁ " << endl ; return 0 ; }