Implement an iterator for a binary search tree that will iterate the nodes by value in ascending order.

Question

m · Accepted Answer

Indeed, an in-order traversal. 

A possible follow-up question would be to do the traversal without using recursion.

GReeky · Answer

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();
	}
}

Rochak · Answer

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.

Apple

Apple Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches