### 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
#include <bits/stdc++.h> 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; }

#### More Articles of Mandeep Sheoran:

Name Views Likes
C++ program to insert an element into binary tree 6240 19
C++ program to find an element into binary tree 772 16
C++ std::is_void 572 15
C++ program to find the closest element in binary search tree 915 19
C++ program to replace every element with the least greater element on its right 573 12
C++ program to delete an element into binary tree 784 24
C++ program to find maximum element between two nodes of binary search tree 699 20
C++ std::remove_copy_if with std::vectors 547 11
C++ program to print duplicate elements from the binary search tree 2937 15
C++ program to find depth of the deepest odd level node in binary tree 575 23
C++ program to remove duplicate elements from the binary search tree 1548 20
C++ std::rotate_copy with std::vector 529 14
C++ std::copy_n with std::vector 638 22
C++ std::copy_if with std::vector 1552 18
C++ program to print all the elements of binary search tree 7105 22
C++ std::reverse_copy with std::list 598 18
C++ program to print all the elements of binary tree 1158 18
C++ program to print all full nodes in a binary tree 572 25
C++ program to find sink odd nodes in binary tree 580 15
C++ std::is_copy_assignable 595 22
C++ program to check whether a binary tree is a full binary tree or not using recursion 609 19
C++ std::is_copy_constructible 618 27
C++ program to delete an element into binary search tree 2873 18
C++ std::reverse_copy with std::vector 487 18
C++ std::rotate with std::vector 641 15
C++ program to check for symmetric binary tree using recursion 599 25
C++ program to maximum sum from a tree with adjacent levels not allowed 551 15
C++ std::copy_n with std::list 594 21
C++ program to check if two trees are identical using recursion 545 15
C++ std::copy_n 873 21
C++ std::copy_if with std::list 998 19
C++ program to print the nodes at odd levels of a tree 562 13
C++ program to find lowest common ancestor in a binary tree 689 29
C++ program to find depth of the deepest odd level leaf node 494 13
C++ std::remove_copy_if with std::list 666 20
C++ program to add all greater values to every node in a given binary search tree 637 15