Apple Interview Question: Implement an iterator for a b... | Glassdoor

Interview Question

Software Engineer Interview Cupertino, CA

Implement an iterator for a binary search tree that will

  iterate the nodes by value in ascending order.
technical, algorithm

Interview Answer

3 Answers


This questions requires you to implement: next inorder successor algorithm for your tree. Implement a method:
Node inorderSuccessor(Node root)

Call this method repeatedly whenever call is made and return the next successor.

Rochak on Mar 25, 2013

Indeed, an in-order traversal.

A possible follow-up question would be to do the traversal without using recursion.

m on Feb 5, 2014

public class BSTIterator {

    Queue q;
    BSTIterator(BSTNode root) {
        q = new LinkedList();

    public void insertInorder(BSTNode root) {
        if(root==null) {

    public boolean hasNext() {
        return q.size() > 0;

    public BSTNode next() {
        return q.poll();

GReeky on Jan 17, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.