Java amazon interview question : Traverse Binary tree in spiral order

Hi Guys,

Recently i got interviewed by amazon and got below question in the programming round (First round).

Traverse binary tree in spiral order.

output is : 30,40,20,15,25,35,45,46,43,36,33,26,22,16,7.

And also interviewer want optimized solution for the above problem.

Here i am submitting the optimized solution after discussing with 15 year experienced guy in data structure.

The optimized solution is storing child reference in either right or left direction at runtime while traversing the parent node value.

Example:


public class TraverseTreeInSpiral {

  public static void main(String[] args) {
    new TraverseTreeInSpiral().run();
  }

  static class Node {
    Node left;
    Node right;
    int value;
    Node next;  // to store child node reference at runtime
    public Node(int value) {
      this.value = value;
    }
  }

  public void run() {
    // build the simple tree
    Node root = new Node(30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 15);
    insert(root, 25);
    insert(root, 35);
    insert(root, 45);
    insert(root, 7);
    insert(root, 16);
    insert(root, 22);
    insert(root, 26);
    insert(root, 33);
    insert(root, 36);
    insert(root, 43);
    insert(root, 46);
    TravesreTreeInSpiralOrder(root, true);
  
  }

  public void insert(Node node, int value) {
    if (value < node.value) {
      if (node.left != null) {
        insert(node.left, value);
      } else {
        System.out.println("  Inserted " + value + " to left of "
            + node.value);
        node.left = new Node(value);
      }
    } else if (value > node.value) {
      if (node.right != null) {
        insert(node.right, value);
      } else {
        System.out.println("  Inserted " + value + " to right of "
            + node.value);
        node.right = new Node(value);
      }
    }
  }


public void TravesreTreeInSpiralOrder(Node root, boolean right) {
Node row = null;   // storing horizontal node from right or left direction ie. storing child node reference at runtime
while (root != null) {
System.out.println(root.value);  // Value of the tree in spiral order
Node first = null;
Node second = null;
if (right == true) {
first = root.left;
second = root.right;
} else {
first = root.right;
second = root.left;
}
if(first!=null) {
row = addtoEndRow(row, first);
}
if(second!=null) {
row = addtoEndRow(row, second);
}
root = root.next;
}
 right = !right;
 if(row!=null)
 TravesreTreeInSpiralOrder(row, right);

}

public Node addtoEndRow(Node row,Node value) {
value.next = row;
return value;
}

}
        

Click to Read more Data structure questions and answer

If you like the above solution . Please share this blog