Java ArrayList solution

  • 1
    public class BSTIterator {
    TreeNode root;
    ArrayList<Integer> ls = new ArrayList<Integer>();
    int point = 0;
    int n = 0;
    public BSTIterator(TreeNode root) {
        this.root = root;
        n = ls.size();
    private void inorder(TreeNode root) {
        if(root == null) return;
        if(root.left != null) inorder(root.left);
        if(root.right != null) inorder(root.right);
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(point < n) return true;
        else return false;
    /** @return the next smallest number */
    public int next() {
        return ls.get(point++);


    1. use inorder to traverse the tree and save in ArrayList when initiate iterator
    2. hasNext() means check whether point in the size of list
      next() means move point in list

    I guess moving point in list is quicker than pop() in stack.

  • 0

    You are using more than O(h) memory

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.