Sink Zeros in Binary Tree

https://www.techiedelight.com/sink-nodes-containing-zero-bottom-binary-tree/

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.

The time complexity of above solution is O(n2) and need O(h) extra space for the call stack where h is the height of the tree.

// 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);

}

X. https://github.com/writecoffee/algorithms/blob/master/algo4/tree/traversal/tr_trav_sink_zeros.java

  public void sink(TreeNode root) {

    explore(root, new LinkedList<TreeNode>());

  }

  private void explore(TreeNode c, LinkedList<TreeNode> q) {

    if (c == null) {

      return;

    }

    explore(c.left, q);

    explore(c.right, q);

    if (c.val == 0 && !q.isEmpty()) {

      c.val = 1;

      q.poll().val = 0;

    } else if (c.val == 1) {

      q.add(c);

    }

  }

http://janexiehappy.blogspot.com/2014/07/sink-zero-facebook.html
http://jelices.blogspot.com/2014/05/sink-zeros-in-binary-tree.html

 Swap zero value of a node with non-zero value of one of its descendants so that no node with value zero could be parent of node with non-zero.

Solution: 

We use a postorder traversal of the tree where instead of sinking we rise the leafs, we keep the nodes that we are sure that have not a zero ancestor.

public  void sink0(TreeNode root)
 {
  HashSet<TreeNode> finished = new HashSet<TreeNode>();
  sink0(root, new HashMap<TreeNode,TreeNode>(), finished, false);
 }
 
 public void sink0(TreeNode root, HashMap<TreeNode, TreeNode> parentMap, HashSet<TreeNode> finished, boolean zerosOver)
 {
  if(root.val==0)
   zerosOver = true;
  if(!zerosOver)
   finished.add(root);
  
  if(root.left != null)
  {
   parentMap.put(root.left, root);
   sink0(root.left, parentMap, finished, zerosOver);
  }
  if(root.right != null)
  {
   parentMap.put(root.right, root);
   sink0(root.right, parentMap, finished, zerosOver);
  }
  if(root.val!=0 && !finished.contains(root))
  {
   TreeNode temp = root;
   ArrayDeque<TreeNode> nonZeroNodes = new ArrayDeque<TreeNode>();
   ArrayDeque<TreeNode>nodes = new ArrayDeque<TreeNode>();
   while(temp!=null && !finished.contains(temp))
   {
    nodes.push(temp);
    if(temp.val!=0)
     nonZeroNodes.push(temp);
    temp = parentMap.get(temp);
   }
   
   while(!nonZeroNodes.isEmpty())
   {
    TreeNode tempNode = nonZeroNodes.pop();
    TreeNode toModify = nodes.pop();
    toModify.val = tempNode.val;
    finished.add(toModify);
   }
   while(!nodes.isEmpty())
   {
    TreeNode toModify = nodes.pop();
    toModify.val=0;
   }
  }
 }