SHARE
TWEET

Untitled

a guest Dec 2nd, 2019 92 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //== Node.java
  2. public class Node {
  3.     Node left;
  4.     Node right;
  5.     public int value;
  6.  
  7.     public Node(int v) {
  8.         value = v;
  9.     }
  10. }
  11.  
  12. //=== BSTIterator.java
  13. class BSTIterator {
  14.  
  15.     private Node root;
  16.  
  17.     public BSTIterator(final Node node) {
  18.         root = node;
  19.     }
  20.  
  21.     public int next() {
  22.         Node pn = root;
  23.         Node cn = root;
  24.  
  25.         while (cn.left != null) {
  26.             pn = cn;
  27.             cn = cn.left;
  28.         }
  29.  
  30.         if (pn == cn) {
  31.             root = root.right;
  32.         } else if (cn.right != null) {
  33.             pn.left = cn.right;
  34.         } else {
  35.             pn.left = null;
  36.         }
  37.  
  38.         return cn.value;
  39.     }
  40.  
  41.     public boolean hasNext() {
  42.         return root != null;
  43.     }
  44. }
  45.  
  46. //== BSTIteratorTest.java
  47. import org.junit.Test;
  48.  
  49. import static org.junit.Assert.assertEquals;
  50. import static org.junit.Assert.assertTrue;
  51.  
  52. public class BSTIteratorTest {
  53.  
  54.     @Test
  55.     public void testBSTIterator() throws Exception {
  56.         Node root = new Node(19);
  57.         root.left = new Node(5);
  58.         root.left.left = new Node(2);
  59.         root.left.left.left = new Node(1);
  60.         root.left.left.right = new Node(4);
  61.         root.left.right = new Node(9);
  62.         root.left.right.left = new Node(7);
  63.         root.left.right.right = new Node(14);
  64.         root.right = new Node(33);
  65.         root.right.left = new Node(21);
  66.         root.right.left.left = new Node(20);
  67.         root.right.left.right = new Node(25);
  68.         root.right.left.right.right = new Node(27);
  69.         root.right.right = new Node(38);
  70.         root.right.right.left = new Node(37);
  71.         root.right.right.right = new Node(39);
  72.  
  73.         BSTIterator i = new BSTIterator(root);
  74.         StringBuilder sb = new StringBuilder();
  75.         int prev = -1;
  76.         while(i.hasNext()) {
  77.             int curr = i.next();
  78.             assertTrue(curr > prev);
  79.             sb.append(curr);
  80.             sb.append(' ');
  81.         }
  82.         assertEquals("1 2 4 5 7 9 14 19 20 21 25 27 33 37 38 39 ", sb.toString());
  83.     }
  84. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top