Groupon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
time: O(N)
space: O(lgN) for balanced or O(N) for unbalanced tree
void inorderPrint(){
Node<T> cur = root;
Deque<Node<T>> stack = new ArrayDeque<>();
while( cur != null ){
if( cur.left != null ){
stack.push(cur);
cur = cur.left;
}
else {
print( cur.value );
cur = cur.right;
while( cur == null && ! stack.isEmpty() ){
cur = stack.pop();
print( cur.value );
cur = cur.right;
}
}
}
}
time complexity:O(n)
space complexity:O(1)
void MorrisTraversal(Node *root){
Node *p,prev;
p=root;
if(p==null) return;
while(p!=null){
if(p->left == null)
{print p->data;p=p->right;continue;}
for(prev=p->left;prev->right != null && prev->right !=p;prev=prev->right){}
if(prev->right == null){
prev->right = p; p=p->left;continue;}
if(prev->right == p){
print p->Data;p=p->right;continue;}
}
}
public class InorderIteration {
private static Stack<Node> nodeStack= new Stack<Node>();
private static Set<Node> visited= new HashSet<Node>();
public static void main(String[] args){
Node head = createBST();
System.out.println("Inorder from recursion");
printInorder(head);
nodeStack.add(head);
System.out.println("\nInorder from iteration");
inorder();
}
private static void inorder() {
while(!nodeStack.empty()){
Node curr=nodeStack.pop();
if(visited.contains(curr)){ //to check if its backtracking
System.out.print(curr.getValue()+" ");
visited.remove(curr);
}else{
if(curr.getLeft()==null){
System.out.print(curr.getValue()+" ");
if(curr.getRight()!=null)
nodeStack.push(curr.getRight());
}
else{
if(curr.getRight()!=null)
nodeStack.push(curr.getRight()); //right first
nodeStack.push(curr); //parent
visited.add(curr); // to mark its visited
nodeStack.push(curr.getLeft());//left at last
}
}
}
}
public static Node addToBST(Node node, int value){
if(node==null){
node =new Node();
node.setValue(value);
return node;
}
if(node.getValue()>=value)
node.setLeft(addToBST(node.getLeft(),value));
else
node.setRight(addToBST(node.getRight(),value));
return node;
}
public static void printInorder(Node node){
if(node!=null){
printInorder(node.getLeft());
System.out.print(node.getValue()+" ");
printInorder(node.getRight());
}
}
public static Node createBST(){
Node head=addToBST(null,4);
head=addToBST(head,2);
head=addToBST(head,1);
head=addToBST(head,3);
head=addToBST(head,6);
head=addToBST(head,5);
head=addToBST(head,7);
head=addToBST(head,3);
head=addToBST(head,6);
head=addToBST(head,5);
return head;
}
public static class Node{
private Node left=null;
private Node right=null;
private int value;
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
}
public class TreeNode<T> {
T value;
TreeNode left;
TreeNode right;
public TreeNode(TreeNode left, T value, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
}
import java.util.Stack;
public class TreeIterativeTraversal {
public static <E> void inOrder(TreeNode<E> root) {
if(root == null) {
return;
}
Stack<TreeNode> nodeStack = new Stack<TreeNode>();
nodeStack.push(root);
TreeNode<E> currentNode, currentNodeClone;
while(!nodeStack.isEmpty()) {
currentNode = nodeStack.pop();
if(currentNode.left == null && currentNode.right == null) {
System.out.print(currentNode.value+" ");
continue;
}
if(currentNode.right != null) {
nodeStack.push(currentNode.right);
}
if(currentNode.left == null) {
System.out.print(currentNode.value+" ");
} else {
currentNodeClone = new TreeNode<E>(null, currentNode.value, null);
nodeStack.push(currentNodeClone);
nodeStack.push(currentNode.left);
}
}
}
public static void main(String []args) {
inOrder(root);
}
}
public class TreeNode<T> {
T value;
TreeNode left;
TreeNode right;
public TreeNode(TreeNode left, T value, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
}
import java.util.Stack;
public class TreeIterativeTraversal {
private static TreeNode<Integer> root;
static {
TreeNode<Integer> one = new TreeNode<Integer>(null, 1, null);
TreeNode<Integer> four = new TreeNode<Integer>(null, 4, null);
TreeNode<Integer> eleven = new TreeNode<Integer>(null, 11, null);
TreeNode<Integer> nine = new TreeNode<Integer>(null, 9, null);
TreeNode<Integer> twenty= new TreeNode<Integer>(null, 20, null);
TreeNode<Integer> three = new TreeNode<Integer>(one, 3, four);
TreeNode<Integer> five = new TreeNode<Integer>(three, 5, nine);
TreeNode<Integer> twelve = new TreeNode<Integer>(eleven, 12, null);
TreeNode<Integer> fifthteen = new TreeNode<Integer>(twelve, 15, twenty);
root = new TreeNode<Integer>(five, 10, fifthteen);
}
public static <E> void inOrder(TreeNode<E> root) {
if(root == null) {
return;
}
Stack<TreeNode> nodeStack = new Stack<TreeNode>();
nodeStack.push(root);
TreeNode<E> currentNode, currentNodeClone;
while(!nodeStack.isEmpty()) {
currentNode = nodeStack.pop();
if(currentNode.left == null && currentNode.right == null) {
System.out.print(currentNode.value+" ");
continue;
}
if(currentNode.right != null) {
nodeStack.push(currentNode.right);
}
if(currentNode.left == null) {
System.out.print(currentNode.value+" ");
} else {
currentNodeClone = new TreeNode<E>(null, currentNode.value, null);
nodeStack.push(currentNodeClone);
nodeStack.push(currentNode.left);
}
}
}
public static void main(String []args) {
inOrder(root);
}
}
- Vir Pratap Uttam May 04, 2015