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.
Tags:
technical, algorithm
Answer

Interview Answer

3 Answers

1

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 iterator.next(root) call is made and return the next successor.

Rochak on Mar 25, 2013
2

Indeed, an in-order traversal.

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

m on Feb 5, 2014
1

public class BSTIterator {

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

    public void insertInorder(BSTNode root) {
        if(root==null) {
            return;
        }
        insertInorder(root.left);
        q.add(root);
        insertInorder(root.right);
    }

    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.