Binary Search Tree Iterator

1package pkg5leetcode.interview150;2 3/*4 * Binary Search Tree Iterator | LC 1735 * APPROACH: Stack pushes left spine; pop then push left of right child.6 * COMPLEXITY: Time O(1) amortized, Space O(h)7 */8import java.util.*;9 10public class interview150_LC173BinarySearchTreeIterator {11    /** Same shape as pkg5leetcode/common/TreeNode.java (nested for single-file runs). */12 13    static class TreeNode {14        int val;15        TreeNode left, right;16        TreeNode(int val) { this.val = val; }17    }18 19    static class BSTIterator {20        Deque<TreeNode> st = new ArrayDeque<>();21 22        BSTIterator(TreeNode root) {23            pushLeft(root);24        }25 26        int next() {27            TreeNode n = st.pop();28            pushLeft(n.right);29            return n.val;30        }31 32        boolean hasNext() { return !st.isEmpty(); }33 34        void pushLeft(TreeNode node) {35            while (node != null) {36                st.push(node);37                node = node.left;38            }39        }40    }41 42    public static void main(String[] args) {43        TreeNode root = new TreeNode(7);44        root.left = new TreeNode(3);45        root.right = new TreeNode(15);46        root.right.left = new TreeNode(9);47        root.right.right = new TreeNode(20);48        BSTIterator it = new BSTIterator(root);49        check(it.next() == 3, "case1");50        check(it.next() == 7, "case2");51        check(it.hasNext(), "case3");52        check(it.next() == 9, "case4");53        System.out.println("all tests passed");54    }55 56    static void check(boolean cond, String name) {57        if (!cond) throw new AssertionError("FAILED: " + name);58        System.out.println("  PASS " + name);59    }60}