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

Pergunta de entrevista da empresa Apple

Respostas da entrevista

Empresas seguidas

Buscas de vagas