Find depth of the deepest odd level leaf node | C ++ program to find depth of the deepest odd level leaf node ; A utility function to find maximum of two integers ; A Binary Tree node ; A utility function to allocate a new tree node ; A recursive function to find depth of the deepest odd level leaf ; Base Case ; If this node is a leaf and its level is odd , return its level ; If not leaf , return the maximum value from left and right subtrees ; Main function which calculates the depth of deepest odd level leaf . This function mainly uses depthOfOddLeafUtil ( ) ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int max ( int x , int y ) { return ( x > y ) ? x : y ; } struct Node { int data ; struct Node * left , * right ; } ; struct Node * newNode ( int data ) { struct Node * node = ( struct Node * ) malloc ( sizeof ( struct Node ) ) ; node -> data = data ; node -> left = node -> right = NULL ; return node ; } int depthOfOddLeafUtil ( struct Node * root , int level ) { if ( root == NULL ) return 0 ; if ( root -> left == NULL && root -> right == NULL && level & 1 ) return level ; return max ( depthOfOddLeafUtil ( root -> left , level + 1 ) , depthOfOddLeafUtil ( root -> right , level + 1 ) ) ; } int depthOfOddLeaf ( struct Node * root ) { int level = 1 , depth = 0 ; return depthOfOddLeafUtil ( root , level ) ; } int main ( ) { struct 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 ) ; cout << depthOfOddLeaf ( root ) << " ▁ is ▁ the ▁ required ▁ depth " ; getchar ( ) ; return 0 ; }