Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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;
}
}
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;
}
For zero current descendant we need to check for some more level down upto we don't get a non zero value or all possible descendants are zero
and copy non zero value to all possible sequential parents having value zero.
to achieve this a almost complete sub tree traversal is required for each node
0
0 0
2 3 4 5
@anil1in7 logic is fine except 1 change
preorder Traversal{
preorder left;
preorder right;
IF(parent == zero && non-zerochild)
swap;
}
This will work for the case given by @sunny
@anonymous
your solution is also wrong try this
0
1 2
3 4 5 6
both of your codes will not propagate 0 downwards
preorder Traversal{
preorder left;
preorder right;
IF(parent == zero && non-zerochild)
{
swap;
if(left-non-zero)
preorder left;
else
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
I thought about this more and I think it could potentially shift a 0 around a single level of the tree, which is probably not desired. The solution is to record the depth of a node in the Node class and, in the zerosink function, only actually perform the swap if the nonzero node is actually at a greater depth than the zero node.
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();
We should use a queue instead of a stack in order to swap always the top-most zero. Take this case for example:
0
/
0
/ \
2 0
i don't know how much complexity wise it will be different as the soln i gave is anyway O(n) .. the good thing with stack is it always keep a portion of tree as required.. while in case of queue you will have to abruptly empty the queue if there are only zeros
please try the solution using queue, To keep track of zero present is a bit messy .. will be interesting
The complexity is the same but your algorithm doesn't work (in the example that I gave you the 2 only goes up one level). But you are correct that using a queue is not a good idea... furthermore, we wouldn't keep the relative order of the non-zero nodes. I think if we use a stack and process the tree in postorder it works:
void sinkzero(Node& node, stack<int>& s) {
if (node == null) return;
if (node->val == 0) s.push(node);
sinkzero(node->left, s);
sinkzero(node->right, s);
if (!s.empty()) {
if (node->val != 0) swap(node->val, s.top()->val);
s.pop(); // if node->val == 0 then s.top() must be this node
}
}
Nevermind, it still doesn't work well. I can't see a O(n) solution that mantains the relative order of the non-zero nodes right now :\
You are right, I forgot completely about them :)
void sinkzero(Node& node, deque<int>& d) {
if (node == null) return;
if (node->val == 0) d.push_back(node);
else {
swap(node->val, d.front()->val);
d.pop_front();
d.push_back(node);
}
sinkzero(node->left, d);
sinkzero(node->right, d);
if (!d.empty() && d.back() == node) d.pop_back();
}
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);
}
}
This can be achieved using post-order traversal -
- Biru January 22, 2014