Facebook | Onsite | Tree Iterator
Sithis
9019
TreeMetaIteratorOnsiteInterview

Question:
https://leetcode.com/problems/binary-search-tree-iterator

Follow-up 1:
Assume BSTIterator is a library class. You need to extend the functionality of this class by implementing 2 methods:

public boolean hasPrev() {
}

/** Can only take 1 step back */
public Integer prev() {
}

Example:

       7
     /   \
    3    15
        /  \
       9    20

ExtendedBSTIterator it = new ExtendedBSTIterator(root);
it.hasNext(); // true
it.next(); // 3
it.next(); // 7
it.next(); // 9
it.next(); // 15
it.hasPrev(); // true
it.prev(); // 9
it.hasPrev(); // false bacause we can only move 1 step back
it.next(); // 15
it.next(); // 20
it.hasNext(); // false
it.hasPrev(); // true
it.prev(); // 15
it.hasNext(); // true
it.next(); // 20
Hint

There are basically 2 ways to do this: composition and inheritance. What are the advantages and disadvantages of one approach over the other?

Follow-up 2:
What if you can move k steps back?

Comments (13)