Visit Leaves In-order
by Isai Damier, Android Engineer @ Google

/****************************************************************
 * Author: Isai Damier
 * Title: Visit Leaves In-order
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Visit/Print the leaves of this BST in order.
 *
 * Time Complexity of Solution:
 *   Best = Average = Worst = O(n).
 *
 * Alternate Algorithm: recursive:
 *
 *     public void leavesInorder(){
 *       leavesInorder(root);
 *     }
 *
 *     public void leavesInorder(Node n){
 *       if(null != n){
 *         leavesInorder(n.left);
 *         if (null == n.left && null == n.right)//isLeaf()
 *         {
 *            visit(n);
 *         }
 *         leavesInorder(n.right);
 *       }
 *     }
 *
 ***************************************************************/ 
 public void leavesInorder() {
  Stack<Node> stack = new Stack<Node>();
  Node n = root;
  while (null != n || !stack.isEmpty()) {
    if (null != n) {
      stack.push(n);
      n = n.left;
    } else {
      n = stack.pop();
      if (null == n.left && null == n.right)//isLeaf()
      {
        visit(n);
      }
      n = n.right;
    }
  }
}

import org.junit.Test;
import static org.junit.Assert.*;

public class BSTTest {

 /**
   * Test of leavesInorder method, of class BST.
   * draw the tree on paper for visual
   */
  @Test
  public void testLeavesInorder() {
    System.out.println(""leavesInorder"");

    final ByteArrayOutputStream output = new ByteArrayOutputStream();
    System.setOut(new PrintStream(output));

    BST bst = new BST();

    String expected = """";
    assertEquals(expected, output.toString());
    expected = ""35\n75\n125\n175\n212\n275\n312\n400\n"";

    //load data into tree
    int[] treeTape = {200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
      175, 225, 275, 325, 375, 35, 212, 312, 400};
    for (int i : treeTape) {
      bst.add(i);
    }
    assertEquals(treeTape.length, bst.size());//has correct size

    //test leavesInorder
    output.reset();
    bst.leavesInorder();//prints to standard output
    assertEquals(expected, output.toString());
    assertEquals(treeTape.length, bst.size());//has correct size
    System.setOut(new PrintStream(new FileOutputStream(FileDescriptor.out)));
    System.out.println(""done with leavesInorder"");
  }
}