C++ program to find depth of the deepest odd level node in binary tree














































C++ program to find depth of the deepest odd level node in binary tree



In Order to solve the above problem, There are two approches:

1.Traverse down the bottom of the binary tree recursively until the node comes which is both leaf node and at an odd level.

2.Traverse down the bottom of the binary tree recursively until the leaf node comes and calculate height .If height comes to be even than return Hieght-1.

 

The first approach seems to be the actual scratch while the second approach is more fundamental.

Disadvantages of First Approch:

1.Time Complexity is high due to more comparisons in checking leafnode and odd level.

2.Requires definition of unnecessary function like CheckLeafNode.

 

Advantages of Second Approch:

1.Takes less time in execution as compared to the first approach.

2.Unneccesary functions need not be defined.

3.Easier to implement and understand.

 

Let%u2019s Look at the algorithm of 2nd approach:

1. If binary tree is empty then return 0.

2. Else

     2(a) Calculate the maximum depth of left subtree recursively

( root=root->left)

     2(b) Calculate the maximum depth of right subtree recursively 

( root=root->right)

     2(c) Find the maximum of maximum depths of left and right

          subtree to find the maximum Hieght of binary tree and 1 for the current node.

     2(d) Return maximum depth.

3.If maximum depth is even then return maximum depth-1


Example1:Here we have taken a binary tree with even number of levels.Thus the total height of binary tree is 6.But the deepest odd level node resides at 6-1=5.

Proper Code:

Iostream is one of the most basic C++ libraries! It is used for input and output. 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
using namespace std; 
template <typename T>
  
/* Binary Tree contains nodes at each level that contain data ,
refrence to left child and refrence to right child*/
class Node 
{  
    public: 
    T object; 
    Node* left;  
    Node* right;  
    Node<T>()               /*default constructor*/
   {
    left=NULL;
    right=NULL;
   }
   
    Node<T>(T data)                /*paramaterized constructor*/
   {  
    Node<T>* newnode = new Node<T>(); 
    newnode->object = data;  
    newnode->left = NULL;  
    newnode->right = NULL;   
   } 
   ~Node()    /*destructor*/
   {
    delete[] left,right; 
    }

};  
  /* Function to add a new node to Binary Tree */
template <typename T>
Node<T>* makeNewNode(T data)  
{  
    Node<T>* newnode = new Node<T>();      /*adding a new node to binary tree*/
    newnode->object = data;  
    newnode->left = NULL;  
    newnode->right = NULL;  
      
    return(newnode);  
}  
/* Function to calculate maximum hieght of Binary Tree */
template <typename T>
int CalcDepth(Node<T>* node)  
{  
    if (node == NULL)  /*Checking whether the node is null */
        return 0;  
    else
    {  
       
        int leftSubDepth = CalcDepth(node->left);  /*calculating recursively each subtree's hieght*/
        int rightSubDepth = CalcDepth(node->right);  
      
        /* use the larger one */
        if (leftSubDepth > rightSubDepth)  /*updating hieght at each call*/
            return(leftSubDepth + 1);  
        else return(rightSubDepth + 1);  
    }  
}  
  
     
int main()  //Driver Function
{  
    Node<int> *root = new Node<int>(5);  /*adding a node through paramaterized constructor*/
    
    root->left = makeNewNode(15);        /*adding a node through makeNewNode function*/
    root->right = makeNewNode(42);  
    root->left->left = makeNewNode(11);  
    root->left->left->left = makeNewNode(60);  
    root->left->left->right=makeNewNode(34);
    root->right->right=makeNewNode(6);
    root->right->left=makeNewNode(3);
    root->right->left->right=makeNewNode(49);
    root->right->left->right->left=makeNewNode(2); /*The following tree is shown in example 1*/

    if(CalcDepth(root)%2==0)                            /*if maximum depth of tree is even than print one depth less*/
   { cout << "Depth of deepest Odd Level node is " << (CalcDepth(root)-1);}
    else
    cout << "Depth of deepest Odd Level node is " << (CalcDepth(root));
    return 0;
}  
 

Output of Example 1:

From the command Prompt.

Let's look at another

Example:

Example 2:

Here we have modified the above tree.Now the total number of levels in binary tree are 5.Since they are odd,the maximum

hieght of binary tree is 5.Hence the deepest odd level node resides atlevel 5. 

Output of Example 2:

From the command Prompt.

Analysis of the above code:

Time Complexity is O(n).(This is because we are traversing each and every node).

Space Complexity is O(n).

 Hope that the explaination works.


More Articles of Adit Alware:

Name Views Likes
C++ program to find depth of the deepest odd level node in binary tree 165 3

Comments

  • Jainil
    22-Aug-2019 10:02:57 PM
    Good Concept and explained nicely.
  • Pawan
    22-Aug-2019 09:54:06 PM
    Explained Perfectly!!