Directi Interview Question Software Engineer / Developers
0of 0 votesConstruct a BST and do its zigzag traversal.
Country: India
Interview Type: Written Test
import java.io.IOException;
import java.util.ArrayList;
class TreeNode {
public TreeNode levelnext,next,left, right;
public int data;
TreeNode(int data) {
this.data = data;
}
}
public class ZIGZAGTRAVERSAL {
public static TreeNode getRandomBST() {
TreeNode mainroot = new TreeNode(7);
TreeNode root = mainroot;
root.left = new TreeNode(5);
root.right = new TreeNode(12);
root.left.left = new TreeNode(3);
root.left.left.left = new TreeNode(2);
root.left.right = new TreeNode(6);
root.left.left.right = new TreeNode(4);
root.right.left = new TreeNode(10);
root.right.right = new TreeNode(14);
return mainroot;
}
public static void zigZag(TreeNode node) {
int direction = 1;
ArrayList<TreeNode> alist = new ArrayList<TreeNode>();
alist.add(node);
int count1 = 1;
int count2 = 0;
while (alist.size() > 0) {
if (direction == 1) {
for (int i = 0; i < count1; i++) {
TreeNode n = alist.get(i);
if (n.left != null) {
count2++;
alist.add(n.left);
}
if (n.right != null) {
count2++;
alist.add(n.right);
}
}
for (int i = 0; i < count1; i++) {
System.out.print(alist.get(0).data + " ");
alist.remove(0);
}
count1 = 0;
} else {
int pos2 = alist.size() - 1;
int pos1 = alist.size() - count2;
for (int i = pos1; i <= pos2; i++) {
TreeNode n = alist.get(i);
if (n.left != null) {
count1++;
alist.add(n.left);
}
if (n.right != null) {
count1++;
alist.add(n.right);
}
}
for (int i = pos2; i >= pos1; i--) {
System.out.print(alist.get(i).data + " ");
alist.remove(i);
}
count2 = 0;
}
direction = direction ^ 1;
}
}
public static void main(String args[]) throws IOException {
TreeNode bst = getRandomBST();
zigZag(bst);
}
}
even though this uses a single arraylist, it does not mean that this is space efficient.
If you compare two stack implementation and this implementation,
you can see at all stages , both implementations uses the same memory.
More over, since this implementation takes little more time than the other, as it removes elements from one index to another.
and the implementation of two stacks.. is easier to read and implement
U r rite but the remove thing might not be true
* The solution are identical apart from the fact that u have to explicitly maintain 2 stacks i dont do that and travesre the arraylist in opposite direction.
* Secondly i manage things using 1 object only in ur case an extra object has to be maintained
private static void zigzag(Node node) {
- Anonymous June 07, 2012Stack<Node> currentStack = new Stack<Node>();
Stack<Node> nextStack = new Stack<Node>();
currentStack.add(node);
zigzag(currentStack, nextStack, true);
}
private static void zigzag(Stack<Node> currentStack, Stack<Node> nextStack,
boolean reverse) {
while(!currentStack.isEmpty()){
Node pop = currentStack.pop();
System.out.println(pop);
if(reverse){
if(pop.left != null)
nextStack.push(pop.left);
if(pop.right != null)
nextStack.push(pop.right);
}else{
if(pop.right != null)
nextStack.push(pop.right);
if(pop.left != null)
nextStack.push(pop.left);
}
zigzag(nextStack, currentStack, !reverse);
}
}