C++ program to find depth of the deepest odd level node in binary tree
Description:
This Program is to find depth of the deepest odd level node in binary tree
For Example:
Input :
The Elements are : 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8
1
/ \
2 3
/ / \
4 5 6
\
7
\
8
Output :
Required depth : 5
Program :
//C++ program to find depth of the deepest odd level node in binary tree
using namespace std;
// Tree node
struct Node
{
int data;
Node *left, *right;
};
// Returns a new tree Node
Node* newNode(int data)
{
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Is a leaf or not
bool isleaf(Node *root)
{
return (root->left == NULL && root->right == NULL);
}
// Find depth of the deepest odd level leaf
int depthUntil(struct Node *root, int level)
{
// Base Case
if (root == NULL)
return 0;
// Increment current level
level += 1;
// If this node is a leaf and its level is odd, return its level
if (level%2 != 0 && isleaf(root))
return level;
return max(depthUntil(root->left, level),
depthUntil(root->right, level));
}
// Calculates the depth of deepest odd level leaf.
int depthOdd(Node *root)
{
return depthUntil(root, 0);
}
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->right->right = newNode(7);
root->right->right->right->right = newNode(8);
cout << " Required depth : " << depthOdd(root) ;
getchar();
return 0;
}
Comments