Sink Zero -- Facebook

Question:

Sink zero in Binary tree. Swap '0' value node with non-zero value node and its descendants so that no node with value '0' could be parent of node with non-zero.

Example:

Answer:
#include <stdio.h>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

struct BTNode{
int val;
BTNode *left;
BTNode *right;
BTNode(int v): val(v),left(NULL),right(NULL){}
};

void postorder0(BTNode *);

void printTree(BTNode *root,int level){
   if(!root) return;

   printTree(root->left, level-1);

   for(int i=0; i<level; i++) {
     cout << "  ";
   }
   cout << root->val << endl;
 
   printTree(root->right, level-1);
   return;
}

void sinkZero(BTNode *root){
postorder0(root);
}

void preorder0 (BTNode *root){
if(!root) return;

if(root->val == 0){
if(root->left && root->left -> val!=0){
swap(root->val, root-> left->val);
preorder0(root->left);
}
else if(root->right && root->right->val != 0){
swap(root->val, root-> right->val);
   preorder0(root->right);
}
}
return;
}

void postorder0 (BTNode *root){
if(!root) return;

postorder0(root->left);
postorder0(root->right);

if(root->val == 0){
if(root->left && root->left->val!=0  || root->right && root->right->val!= 0){
preorder0(root);
}
}
return;
}

int main(){
BTNode *root = new BTNode (0);
root->left = new BTNode (0);
root->right = new BTNode (0);
root->left->left = new BTNode (0);
root->left->right = new BTNode (2);
root->right->left = new BTNode (3);
root->right->right = new BTNode (0);
root->left->left->left = new BTNode(0);
root->left->left->right = new BTNode(1);

printTree(root,4);
sinkZero(root);
cout<<endl<<"After sink zero elements down:"<<endl<<endl;
printTree(root,4);
getchar();
return 0;
}