C++ program to find sink odd nodes in binary tree
Description:
This Program is to find sink odd nodes in binary tree
For Example:
Input :
The Elements are : 1 ,2 ,3 ,4 ,5 ,6 ,7
1
/ \
3 5
/ \ / \
2 4 6 8
Output :
2
4 6
3 1 5 8
Program :
// C++ program to find sink odd nodes in binary tree
using namespace std;
// tree node
struct Node
{
int data;
Node *left, *right;
};
// returns a new tree Node C++ program to find sink odd nodes in binary tree
Node* newNode(int data)
{
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Helper function to check if node is leaf node
bool isLeaf(Node *root)
{
return (root->left == NULL && root->right == NULL);
}
// to sink a tree with odd root
void sink(Node *&root)
{
// If NULL or is a leaf, do nothing
if (root == NULL || isLeaf(root))
return;
// if left child is even
if (root->left && !(root->left->data & 1))
{
// swap root's data with left child
swap(root->data, root->left->data);
sink(root->left);
}
// if right child is even
else if(root->right && !(root->right->data & 1))
{
// swap root's data with right child
swap(root->data, root->right->data);
sink(root->right);
}
}
// Calls sink() if any odd node is found
void sinkOdd(Node* &root)
{
// If NULL or is a leaf, do nothing
if (root == NULL || isLeaf(root))
return;
// Process left and right subtrees
sinkOdd(root->left);
sinkOdd(root->right);
// If root is odd, sink it
if (root->data & 1)
sink(root);
}
//This function is used for displaying.
void display(Node* root)
{
queue<Node*> q;
q.push(root);
while (!q.empty())
{
int count = q.size();
// Print one level at a time
while (count)
{
Node *node = q.front();
cout<< node->data<< " ";
q.pop();
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
count--;
}
cout<<endl;
}
}
int main()
{
Node *root = newNode(1);
root->left = newNode(3);
root->right = newNode(5);
root->left->left = newNode(2);
root->left->right = newNode(4);
root->right->left = newNode(6);
root->right->right = newNode(8);
sinkOdd(root);
cout<<"Modified tree after odd nodes are sink\n";
display(root);
return 0;
}
Comments