BFS.java

package practice;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

import practice.BinarySearchTree.Node;

public class BSTPrint {
	
	
	//given a BST print the elements from left to right and top to bottom, and given all keys are different
	
//		25
//	   /  \
//	  15   40
//	 /  \	 \
//  10	 20   50
//		   \
//		    24
	
//	10, 15, 25, 20, 40, 24, 50
	
	//create a hashtable<int leftness, int[] values> that contained lists at each level. 
	//track max and min leftness and print each array going by leftness
//	<Key, value>
//	-2, {10}
//	-1, {15}
//	0, {25,20}
	
	
//		25
//	   /  \
//	  15   40
//	 /  \	 
//10	 20   

//What it does
//25, 15, 10, 20, 40
//What I want
//25, 15, 40, 10, 20

//		25
//	   /  \
//	  15   40
//	 /  \	 \
//  10	 20   50
//		   \
//		    24
	
//	10, 15, 25, 20, 40, 24, 50
	private static class NodeOrder {
		public NodeOrder(Node root, int i) {
			this.value = root;
			this.leftness = i;
		}

		final BinarySearchTree.Node value;
		final int leftness;
	}
	
	public static void main(String[] args)
	{
		BinarySearchTree tree = new BinarySearchTree();
		tree.insert(40);
		tree.insert(50);
//		tree.insert(45);
		tree.insert(15);
		tree.insert(10);
		tree.insert(20);
		tree.insert(24);
    	tree.insert(19);

		Queue<NodeOrder> pendingQ = new ArrayDeque<>();
		ArrayList<NodeOrder> nodes = new ArrayList<>();
		pendingQ.add(new NodeOrder(tree.root, 0));
		while(!pendingQ.isEmpty()) {
			NodeOrder n = pendingQ.poll();
			nodes.add(n);
			if(n.value.left != null) {
				pendingQ.add(new NodeOrder(n.value.left, n.leftness - 1));
			}
			if(n.value.right != null) {
				pendingQ.add(new NodeOrder(n.value.right, n.leftness + 1));
			}
		}
		nodes.sort((a,b) -> Integer.compare(a.leftness, b.leftness));

		for (NodeOrder n : nodes) {
			print(n.value);
			
		}
		
	}

	private static void print(Node n) {
		System.out.print(n.key);
		System.out.print(" ");
	}
	
}

Main.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;


class Main {
 //		  25
//	   /  \
//	  15   40
//	 /  \	 \
//  10	 20   50
//		   /  \
//		 19    24
	
//	10, 15, 25, 20, 40, 24, 50
	private static class OrderedNode {
    int leftness;
    int value;
    int depth;

    OrderedNode(int value, int leftness, int depth) {
      this.leftness = leftness;
      this.depth = depth;
      this.value = value;
    }

    public String toString() {
      return Integer.toString(this.value);
    }
  }
	public static void main(String[] args)
	{
		BinarySearchTree tree = new BinarySearchTree();
				tree.insert(25);
		tree.insert(40);
		tree.insert(50);
//		tree.insert(45);
		tree.insert(15);
		tree.insert(10);
		tree.insert(20);
		tree.insert(24);
    tree.insert(19);
		
		
		ArrayList<OrderedNode> result = orderTree(tree.root, 0, 0);
    for(int i =0; i < result.size(); i++) {
     System.out.print(result.get(i));
      System.out.print(" ");
    
      }
	
		
	}
 
	private static ArrayList<OrderedNode> orderTree(BinarySearchTree.Node n, int leftness, int depth) {
    
    ArrayList<OrderedNode> nodes = new ArrayList<>();
    
		nodes.add(new OrderedNode(n.key, leftness, depth));
    if(n.left != null) {
		
      nodes.addAll(orderTree(n.left, leftness - 1 , depth + 1));
		}
		
		if(n.right != null) {
			 nodes.addAll(orderTree(n.right, leftness + 1, depth + 1));
		}

    //compare by leftness, and then by depth
    nodes.sort((a,b) -> {
      int cmp = Integer.compare(a.leftness,b.leftness);
      if(cmp != 0) return cmp;
      return Integer.compare(a.depth, b.depth);
      });
    return nodes;
	}

	private static void print(BinarySearchTree.Node n) {
		System.out.print(n.key);
		System.out.print(" ");
	}
}