CareerCup

This can be achieved using post-order traversal -

postOrder(BT r) {
  if(r==null)
    return;

  postOrder(r.left);
  postOrder(r.right);

  if(r.val == 0) {
    if(r.left.val != 0) {
       swap(r.val, r.left.val);
    } else {
       swap(r.right, r.right.val);
    }
  }

Just breadth-first traverse the tree, keep all node in a array or list.
Then swap the 0 node from the head of the list and non 0 node from the end of the list:

java codes:

public static void zeroSink(BNode node){
        if (node != null){
            List<BNode> list = new ArrayList<BNode>();
            list.add(node);
            BNode p = node;
            int index = 0;
            while (p != null && index < list.size()){
                p = list.get(index);
                if (p.left != null) list.add(p.left);
                if (p.right != null) list.add(p.right);
                index++;
            }
            int start = 0;
            int end = list.size() - 1;
            BNode n1 = list.get(start);
            BNode n2 = list.get(end);
            while (start < end){
                while (n1.data > 0 && start < end) {
                    start++;
                    n1 = list.get(start);
                }
                while (n2.data == 0 && start < end) {
                    end--;
                    n2 = list.get(end);
                }
                n1.data = n2.data;
                n2.data = 0;
            }
        }

I did not understand very well.
If child node > parent node && parent node = 0, then swap values.
But the child node has children with values larger than 0. So, is the idea to swap recursively by levels?
Could you write an example, please?

from what i understood the main motive is to make sure that no parent with child node or(sub tree) which has none zeros should have value zero.

int search1(tree * node)
{
	if (node == nullptr)
	{
		return 0;
	}
	else if (node->value != 0)
	{
		int t = node->value;
		node->value = 0;
		return t;
	}
	else
	{ 
		int t = search1(node->left);
		if (t!= 0)
		return (t);
		else
		return (search1(node->right));
		
	}
	return 0;
}

void sinkZero(tree **root)
{
	if (*root != nullptr)
	{
		
		if ((*root)->value == 0)
		{
			(*root)->value = search1(*root);
		}
		sinkZero(&(*root)->left);
		sinkZero(&(*root)->right);
	}
}

We can do it like making the heap..
We can use two functions 1)makeheap -> to traverse the tree by postorder traversal and checking the root and its childs. If root is zero then swap it with its nonzero child and apply second function heapify .
2) heapify apply on swapped element and traverse the tree down from there for putting this zero at its proper position . (means if after swapping zero there are child nodes with non zero values then we have to recursively do the same process for all the nodes which are downwords from this swapped zero)

preorder Traversal{
IF(parent == zero && non-zerochild)
swap;

preorder left;
preorder right;
}

This isn't well-tested, but it's the same general idea as beartung's post, which is to order the nodes according to level using breadth-first search. I separated the traversal from the zero-sinking so the algorithm is clearer.

class Node:
	left = None
	right = None
	data = 0

	def __repr__(self):
		s = "(" + str(self.data) + ", "
		s += str(self.left) + ", "
		s += str(self.right) + ")"
		return s


def bfs(root):
	queue = [root]
	idx = 0
	while idx < len(queue):
		n = queue[idx]
		if n.left:
			queue.append(n.left)
		if n.right:
			queue.append(n.right)
		idx += 1
	return queue


def zerosink(queue):
	start = 0
	end = len(queue) - 1
	while start < end:
		if queue[start].data == 0 and queue[end].data > 0:
			queue[start].data = queue[end].data
			queue[end].data = 0
			start += 1
			end -= 1
		elif queue[start].data == 0 and queue[end].data == 0:
			end -= 1
		else:
			start += 1
	return queue

Some thoughts.

For N node and possibility of multiple zeros, the worst case scenario appears to be N^2, i.e. we blindly look for a zero and when found we sink it to the bottom of the current subtree (square because for a degenerate tree, i.e. a tree is a list, it's N^2).

Alternatively we may look for the first non-zero child and swap with it and repeat. This may improve N^2 but I am not positive by how much.

Sinking N zeros is sinking of 1 zero N times, thus since sinking 1 is at worst N (if we have to traverse the whole tree and find no zero) then sinking N is N^2.

Solution O(n)

std::stack ss;
preorder Traversal{ 
IF(parent == zero) 
{
	ss.push(parent);

}
else
{
	if(!ss.empty())
	  {
		swap(ss.top(),parent)
		ss.pop();
                 ss.push(parent);
	 }
}
	preorder left;
	preorder right;
	if(ss.top()==parent)
		ss.pop();

public class SinkZero {
	
	private static class Node<K> {
		public K data;
		public Node<K> left;
		public Node<K> right;
		
		public Node(K data, Node<K> left, Node<K> right) {
			this.data = data;
			this.left = left;
			this.right = right;
		}
		
		@Override
		public String toString() {
			return "Data:"+data;
		}
	}
	
	public static void sinkZero(Node<Integer> root) {
		if(root != null) {
			Stack<Node<Integer>> zeroStack = new Stack<Node<Integer>>();
			
			if(root.data == 0) {
				zeroStack.push(root);
			}
			
			if(root.left != null) {
				sinkZero(root.left, zeroStack);
			}
			if(root.right != null) {
				sinkZero(root.right, zeroStack);
			}
		}
	}
	
	public static void sinkZero(Node<Integer> node, Stack<Node<Integer>> zeroStack) {
		
		//do a postorder traversal. in pre recurssion if the data is zero add to stack
		//in post recursion step pop from queue and swap it with the node
		
		if(node.data == 0) {
			zeroStack.push(node);
		}
		
		if(node.left != null) {
			sinkZero(node.left, zeroStack);
		}
		if(node.right != null) {
			sinkZero(node.right, zeroStack);
		}
		
		if(zeroStack.size() > 0) {
			Node<Integer> zeroNode = zeroStack.pop();
			zeroNode.data = node.data;
			node.data = 0;
		}
	}
	
	private static void printTree(Node tree) {
		if(tree == null) {
			System.out.print("Null tree");
		} else {
			Queue<Node> currentLevel = new LinkedList<Node>();
			Queue<Node> nextLevel = new LinkedList<Node>();
			
			currentLevel.add(tree);
			printTreeBFS(currentLevel,nextLevel);
		}
	}
	
	private static void printTreeBFS(Queue<Node> currentLevel, Queue<Node> nextLevel) {
		if(currentLevel.size() > 0) {
			Node elem = currentLevel.poll();
			if(elem.left != null) {
				nextLevel.add(elem.left);
			}
			if(elem.right != null) {
				nextLevel.add(elem.right);
			}
			System.out.print("Data:"+elem.data+"    ");
			if(currentLevel.size() == 0) {
				Queue<Node> temp = currentLevel;
				currentLevel = nextLevel;
				nextLevel = temp;
				System.out.println();
			}
			printTreeBFS(currentLevel, nextLevel);
		}
	}
	
	public static void main(String[] args) {
		//create a dummy tree
		Node<Integer> tree1 = new Node<Integer>(0,new Node<Integer>(0,new Node<Integer>(2,null,null),new Node<Integer>(3,null,null)),new Node<Integer>(0,new Node<Integer>(4,null,null),new Node<Integer>(5,null,null)));
		
		printTree(tree1);
		
		sinkZero(tree1);
		
		printTree(tree1);
	}
}

public static NodeBT postOSink(NodeBT root){
		if(root!=null){
		postOSink(root.left);
		postOSink(root.right);
		if(root.data==0){
			if(root.left!=null && root.left.data!=0){
				root.data=root.left.data;
				root.left.data=0;
			}
			else if(root.right!=null && root.right.data!=0)
				{
				root.data=root.right.data;
				root.right.data=0;
				}
		}
		}
		return root;

}

How about just fix the root node first if it is zero then call the function for to fix nodes for the remaining subtree. The root node will ultimately be either the leftmost nonzero node or right-most non zero node.
It will take O(n) time.


public void sinkZeroes(Node root){
if(root.data==0){
if(root.leftChild!=null && root.leftChild.data!=0){
int temp = root.data;
root.data = root.leftChild.data;
root.leftChild.data = temp;
}
else if(root.rightChild!=null && root.rightChild.data!=0){
int temp = root.data;
root.data = root.rightChild.data;
root.rightChild.data = temp;
}
}
sinkZeroes1(root);
}

//sink in zeroes in binary tree
public void sinkZeroes1(Node root){
if(root==null)
return;
sinkZeroes1(root.leftChild);
sinkZeroes1(root.rightChild);
System.out.println(root.data);
if(root.data==0){
if(root.leftChild!=null && root.leftChild.data!=0){
int temp = root.data;
root.data = root.leftChild.data;
root.leftChild.data = temp;
}
else if(root.rightChild!=null && root.rightChild.data!=0){
int temp = root.data;
root.data = root.rightChild.data;
root.rightChild.data = temp;
}
}
}

I have implemented a postorder solution where we rise leafs. I have tested and seems to work fine. (Solution at jelices.blogspot.com/2014/05/sink-zeros-in-binary-tree.html)

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;
			}
		}
	}

I think this is more of a data structure question:

appropriate data structure for such problems is heap, represented in an array
now apply pseudo delete operation on nodes with key zero(non null), similar to what we do during heap sort


If we have to do it in a binary tree data structure, then approach would be:
do post order traversal and when processing root, sink root to the subtree which has a non zero root

The problem can be solved through rotations (remember, if you deal with BST, no simple swaps are allowed, since it breaks BST properties!). So, what you need it to do POST-ORDER traversal of a tree. As soon as you meet a 0 element, you simply perform left or right rotations till element children are either 0s and/or nulls (rotations explanation can be easily found in Google). The important propert of rotations for us is that it sinks one level the element for which the rotation is applied, while preserving the properties of BST. The post-order traversal guarantees that when you arrive to a given element, all 0s in its branches are already sunk, and so you guarantee that all zeroes in the tree in the end are at the bottom!

Preorder + Queue:(On)

public void sink(Node root){
	Queue queue = new LinkedList<Node>();
	helper(root, queue);
}

public void helper(Node root, Queue q){
	if(root == null){
		return;
	}
	if(root.val == 0){
		q.add(root);
	}
	else{
		if(!q.empty()){
			swap(q.poll(), root);
		}
		q.add(root);
	}
	helper(root.left, q);
	if(q.peek() == root.left){
		q.remove();
	}
	helper(root.right, q);
	if(q.peek() == root.right){
		q.remove();
	}
}

Preorder + Queue:(On)

public void sink(Node root){
	Queue queue = new LinkedList<Node>();
	helper(root, queue);
}

public void helper(Node root, Queue q){
	if(root == null){
		return;
	}
	if(root.val == 0){
		q.add(root);
	}
	else{
		if(!q.empty()){
			swap(q.poll(), root);
		}
		q.add(root);
	}
	helper(root.left, q);
	if(q.peek() == root.left){
		q.remove();
	}
	helper(root.right, q);
	if(q.peek() == root.right){
		q.remove();
	}
}

Can be done with a variation on dfs, keep track of number of zeroValuedNodes along path from root on a stack, if at a leaf that has non zero value swap with head of stack

If zeroValuedNodes not empty at the end, there is no solution

Outline would be:
sinkZero(Node r){
init stack zeroValuedNodes
dfs(r, zeroValuedNodes)
if stack not empty problem not solvable
}

dfs(Node n, zeroValuedNodes){
if leaf {
if non zero, swap value with head of stack, pop zeroValuedNodes
return
} else {
if zero push onto zeroValuedNodes
if leftChild exists, dfs(left,..)
if rightChild exists, dfs(right,..)
}
return
}

// returns true if swap was performed
// Time: O(n)
	
	public boolean sinkZero(TreeNode node, TreeNode parent, boolean shouldSwap)
	{
		if (node == null)
		{
			return false;
		}
		boolean isSwap = false;
		
		if (node.getValue() != 0)
		{
			if (shouldSwap)
			{
				swapNodes(parent, node);
				isSwap = true;
			}
			// if shouldswap = true, we should send it to the sub-tree because now node value = 0
			
			boolean childSwap = sinkZero(node.getLeft(), node, shouldSwap);
			
			// if child swap was performed, it's mean that the node.value was swapped and we don't need to swap it again
			sinkZero(node.getRight(), node, shouldSwap && !childSwap);
			
			return isSwap;
		}
		// node value == 0
		
		boolean childSwapped1 = sinkZero(node.getLeft(), node, true);
		boolean childSwapped2 = sinkZero(node.getRight(), node, !childSwapped1);
		// check if shouldSwap = true and one of the children performed a swap, we will swap with him the node value
		// this scenario raise up the non zero value
		if (shouldSwap && (childSwapped1 || childSwapped2))
		{
			swapNodes(node, parent);
			isSwap = true;
		}
		return isSwap;
	}

	private void swapNodes(TreeNode n1, TreeNode n2)
	{
		int tmp = n1.getValue();
		n1.setValue(n2.getValue());
		n2.setValue(tmp);
	}

I will try to put a pseudo code.

sinkZero(root)
{
	if (root == null) return;
	if (root.left == null && root.right == null) return;

	sinkZero(root.left);
	sinkZero(root.right);
	
	if (root.value == 0 && root.left.value !=0)
	{
		swapValues(root, root.left);
		sinkZero(root.left)
	}

	if (root.value == 0 && root.right.value !=0)
	{
		swapValues(root, root.right);
		sinkZero(root.right)
	}
}

O(nlogn)

Use a Preorder traversal approach, if both childs have zero means we can not zink any more

public void ZinkZeros(TreeNode root)
{
	if (root == null)
		return;

	ZinkZeros(root.Left);
	ZinkZeros(root.Right);

	// If both childs are Zero we stop the recurzion, all zeros are sink
	if ((root.Left != null || root.Left.Value == 0) && (root.Right != null || root.Right.Value == 0))
		return;

	if (root.Value == 0)
	{
		if (root.Left != null && root.Left.Value != 0)
			SwapValues(root, root.Left);
		else if (root.Right != null && root.Right.Value != 0)
			SwapValues(root, root.Right);
	}
}

Well I think we should do post order traversal so that we start searching from the bottom of the tree. Every time we find 0 which any of the children is different from 0 do the following relocation:
1) Swap not 0 child with the 0 parent
2)Repeat 1 point till both children of 0 parent are also equal 0 or 0 parent is leaf node.