Sink Odd nodes in Binary Tree | Program to sink odd nodes to the bottom of binary tree ; A binary tree node ; Helper function to allocates a new node ; Helper function to check if node is leaf node ; A recursive method to sink a tree with odd root This method assumes that the subtrees are already sinked . This method is similar to Heapify of Heap - Sort ; If NULL or is a leaf , do nothing ; if left subtree exists and left child is even ; swap root 's data with left child and  fix left subtree ; if right subtree exists and right child is even ; swap root 's data with right child and  fix right subtree ; Function to sink all odd nodes to the bottom of binary tree . It does a postorder traversal and calls sink ( ) if any odd node is found ; If NULL or is a leaf , do nothing ; Process left and right subtrees before this node ; If root is odd , sink it ; Helper function to do Level Order Traversal of Binary Tree level by level . This function is used here only for showing modified tree . ; Do Level order traversal ; Print one level at a time ; Line separator for levels ; Driver program to test above functions ; Constructed binary tree is 1 / \ 5 8 / \ / \ 2 4 9 10
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; } ; Node * newnode ( int data ) { Node * node = new Node ; node -> data = data ; node -> left = node -> right = NULL ; return node ; } bool isLeaf ( Node * root ) { return ( root -> left == NULL && root -> right == NULL ) ; } void sink ( Node * & root ) { if ( root == NULL || isLeaf ( root ) ) return ; if ( root -> left && ! ( root -> left -> data & 1 ) ) { swap ( root -> data , root -> left -> data ) ; sink ( root -> left ) ; } else if ( root -> right && ! ( root -> right -> data & 1 ) ) { swap ( root -> data , root -> right -> data ) ; sink ( root -> right ) ; } } void sinkOddNodes ( Node * & root ) { if ( root == NULL || isLeaf ( root ) ) return ; sinkOddNodes ( root -> left ) ; sinkOddNodes ( root -> right ) ; if ( root -> data & 1 ) sink ( root ) ; } void printLevelOrder ( Node * root ) { queue < Node * > q ; q . push ( root ) ; while ( ! q . empty ( ) ) { int nodeCount = q . size ( ) ; while ( nodeCount ) { Node * node = q . front ( ) ; printf ( " % d ▁ " , node -> data ) ; q . pop ( ) ; if ( node -> left != NULL ) q . push ( node -> left ) ; if ( node -> right != NULL ) q . push ( node -> right ) ; nodeCount -- ; } printf ( " STRNEWLINE " ) ; } } int main ( ) { Node * root = newnode ( 1 ) ; root -> left = newnode ( 5 ) ; root -> right = newnode ( 8 ) ; root -> left -> left = newnode ( 2 ) ; root -> left -> right = newnode ( 4 ) ; root -> right -> left = newnode ( 9 ) ; root -> right -> right = newnode ( 10 ) ; sinkOddNodes ( root ) ; printf ( " Level ▁ order ▁ traversal ▁ of ▁ modified ▁ tree STRNEWLINE " ) ; printLevelOrder ( root ) ; return 0 ; }