Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //== Node.java
- public class Node {
- Node left;
- Node right;
- public int value;
- public Node(int v) {
- value = v;
- }
- }
- //=== BSTIterator.java
- class BSTIterator {
- private Node root;
- public BSTIterator(final Node node) {
- root = node;
- }
- public int next() {
- Node pn = root;
- Node cn = root;
- while (cn.left != null) {
- pn = cn;
- cn = cn.left;
- }
- if (pn == cn) {
- root = root.right;
- } else if (cn.right != null) {
- pn.left = cn.right;
- } else {
- pn.left = null;
- }
- return cn.value;
- }
- public boolean hasNext() {
- return root != null;
- }
- }
- //== BSTIteratorTest.java
- import org.junit.Test;
- import static org.junit.Assert.assertEquals;
- import static org.junit.Assert.assertTrue;
- public class BSTIteratorTest {
- @Test
- public void testBSTIterator() throws Exception {
- Node root = new Node(19);
- root.left = new Node(5);
- root.left.left = new Node(2);
- root.left.left.left = new Node(1);
- root.left.left.right = new Node(4);
- root.left.right = new Node(9);
- root.left.right.left = new Node(7);
- root.left.right.right = new Node(14);
- root.right = new Node(33);
- root.right.left = new Node(21);
- root.right.left.left = new Node(20);
- root.right.left.right = new Node(25);
- root.right.left.right.right = new Node(27);
- root.right.right = new Node(38);
- root.right.right.left = new Node(37);
- root.right.right.right = new Node(39);
- BSTIterator i = new BSTIterator(root);
- StringBuilder sb = new StringBuilder();
- int prev = -1;
- while(i.hasNext()) {
- int curr = i.next();
- assertTrue(curr > prev);
- sb.append(curr);
- sb.append(' ');
- }
- assertEquals("1 2 4 5 7 9 14 19 20 21 25 27 33 37 38 39 ", sb.toString());
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement