BoundaryTraversal.java

public class BoundaryTraversal {
	public static ArrayList<TNode<Integer>> perform(TNode<Integer> root){
		ArrayList<TNode<Integer>> ret= new ArrayList<TNode<Integer>>();
		ret.addAll(traverseLeftSideTopDown(root));
		ret.addAll(traverseBottomSideLeftRight(root));
		if(root!=null){
			ret.addAll(traverseRightSideBottomUp(root.right));//for excluding root
		}
		return ret;
	}
	/**
	 * Including root, excluding leaf
	 */
	private static LinkedList<TNode<Integer>> traverseLeftSideTopDown(TNode<Integer> root){
		if(root == null || isLeaf(root)) return new LinkedList<TNode<Integer>>();
		else {
			LinkedList<TNode<Integer>> temp= traverseLeftSideTopDown(root.left);
			temp.addFirst(root);
			return temp;
		}
	}
	/**
	 * Including root, excluding leaf
	 */
	private static ArrayList<TNode<Integer>> traverseRightSideBottomUp(TNode<Integer> root){
		if(root == null || isLeaf(root)) return new ArrayList<TNode<Integer>>();
		else {
			ArrayList<TNode<Integer>> temp= traverseRightSideBottomUp(root.right);
			temp.add(root);
			return temp;
		}
	}
	/**
	 * All Leaves
	 */
	private static ArrayList<TNode<Integer>> traverseBottomSideLeftRight(TNode<Integer> root){
		if(root==null){
			return new ArrayList<TNode<Integer>>();
		}
		if(isLeaf(root)){
			ArrayList<TNode<Integer>> curLeaf=new ArrayList<TNode<Integer>>();
			curLeaf.add(root);
			return curLeaf;
		}
		ArrayList<TNode<Integer>> leftHalf=traverseBottomSideLeftRight(root.left);
		ArrayList<TNode<Integer>> rightHalf=traverseBottomSideLeftRight(root.right);
		leftHalf.addAll(rightHalf);
		return leftHalf; 
	}
	private static boolean isLeaf(TNode<Integer> root){
		return root!=null && root.left==null && root.right==null;
	}
}

BoundaryTraversalTest.java

public class BoundaryTraversalTest {
	@Test
	public void testPerform_boundary_1() {
		assertEquals(0, BoundaryTraversal.perform(null).size()); 
		TNode<Integer> r= new TNode<Integer>(100);
		assertEquals(1, BoundaryTraversal.perform(r).size()); 
		assertEquals(new Integer(100), BoundaryTraversal.perform(r).get(0).data); 
		r.left= new TNode<Integer>(50);
		assertEquals(2, BoundaryTraversal.perform(r).size()); 
		assertEquals(new Integer(100), BoundaryTraversal.perform(r).get(0).data); 
		assertEquals(new Integer(50), BoundaryTraversal.perform(r).get(1).data); 
		r.left= null;
		r.right= new TNode<Integer>(150);
		assertEquals(2, BoundaryTraversal.perform(r).size()); 
		assertEquals(new Integer(100), BoundaryTraversal.perform(r).get(0).data); 
		assertEquals(new Integer(150), BoundaryTraversal.perform(r).get(1).data); 
		r.left= new TNode<Integer>(50);
		assertEquals(3, BoundaryTraversal.perform(r).size()); 
		assertEquals(new Integer(100), BoundaryTraversal.perform(r).get(0).data); 
		assertEquals(new Integer(50), BoundaryTraversal.perform(r).get(1).data); 
		assertEquals(new Integer(150), BoundaryTraversal.perform(r).get(2).data); 
	}
	@Test
	public void testPerform_normal_1() {
		TNode<Integer> r= new TNode<Integer>(20);
		r.left= new TNode<Integer>(8);
		r.left.left= new TNode<Integer>(4);
		r.left.right= new TNode<Integer>(12);
		r.left.right.left= new TNode<Integer>(10);
		r.left.right.right= new TNode<Integer>(14);
		r.right= new TNode<Integer>(22);
		r.right.right= new TNode<Integer>(25);
		ArrayList<TNode<Integer>> ans=BoundaryTraversal.perform(r);
		assertEquals(new Integer(20), ans.get(0).data); 
		assertEquals(new Integer(8), ans.get(1).data); 
		assertEquals(new Integer(4), ans.get(2).data); 
		assertEquals(new Integer(10), ans.get(3).data); 
		assertEquals(new Integer(14), ans.get(4).data); 
		assertEquals(new Integer(25), ans.get(5).data); 
		assertEquals(new Integer(22), ans.get(6).data); 
	}
}

TNode.java

public class TNode<K>{
    public K data;
    public TNode<K> left=null;
    public TNode<K> right=null;
    public TNode (K data){
        this.data=data;
    }
}