Guest User

Untitled

a guest
Dec 2nd, 2019
116
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