Get depth of Odd level which contains Leaf node in Binary Tree

The solution is very simple. We need to traverse the tree from root node.

We need to keep track of the current level of the node.

Increment the current level once you go left or right subtree.

Return max depth of an odd level.

Solution in C++

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

int depth_of_odd_level_with_leaf;

void get_depth_of_odd_level_with_leaf(Node *node, int level) 
{
    if (node == NULL) 
    {
      return;
    }

    if (node->left == NULL && node->right == NULL && (level % 2 != 0) && (level > depth_of_odd_level_with_leaf)) 
    {
      depth_of_odd_level_with_leaf = level;
    }

    get_depth_of_odd_level_with_leaf(node->left, level + 1);
    get_depth_of_odd_level_with_leaf(node->right, level + 1);
}

int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    get_depth_of_odd_level_with_leaf(root, 1);

    cout<<"The depth of odd level with leaf = "<<depth_of_odd_level_with_leaf<< endl;

    return 0;  
}  

Output:

The depth of odd level with leaf = 3