Given a binary tree containing many zero nodes, sink nodes having zero value to the bottom of the sub-tree rooted at that node. In other words, the output binary tree should not contain any node having zero value that is parent of node having non-zero value.

For example, binary tree shown on the left can be converted to binary tree shown on the right

The idea is to process the tree nodes in postorder manner, i.e. after fixing left and right subtrees of a node, we fix the node if it is zero. To fix a node, we do something similar to Heapify procedure of Heap sort. As left and right subtree are already fixed, we can fix the binary tree rooted at current node by moving the current node (containing zero) down the tree. We do so by comparing the node with its left and right child and swapping it with the non-zero child and then recursively calling the procedure on the corresponding child. The process is repeated till leaf node is reached or subtree rooted at current node contains all zeroes. As several binary trees can be constructed from one input, below solution would construct any one of them.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Function to sink root node having value 0 to the bottom of the tree // The left and right subtree (if any) of root node are already sinked void sink(Node *root) { // base case: tree is empty if (root == nullptr) return; // if left subtree exists & left child has non-zero value if (root->left && root->left->data != 0) { // swap data of current node with its left child swap(root->data, root->left->data); // recurse for left subtree sink(root->left); } // if right subtree exists & right child has non-zero value else if(root->right && root->right->data != 0) { // swap data of current node with its right child swap(root->data, root->right->data); // recurse for right subtree sink(root->right); } } // Main function to sink nodes having zero value to the bottom // of the binary tree void sinkNodes(Node* &root) { // base case: tree is empty if (root == nullptr) return; // fix left subtree and right subtree first sinkNodes(root->left); sinkNodes(root->right); // sink current node it has value 0 if (root->data == 0) sink(root); } |

The time complexity of above solution is O(n^{2}) and need O(h) extra space for the call stack where h is the height of the tree.

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Please correct me if I’m wrong but I believe you can solve this in O(n) by doing two in-order traversals one left->right and a second one right->left.

I chose in-order as we should prioritize sinking 0 to leftmost elements first.

The double traversal is necessary to address cases such as: