ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

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

prodevelopertutorial October 8, 2020

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
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com
Get top courses from: Educative.io