CareerCup

// Utility function to store vertical order in map 'm' 
    // 'hd' is horizontal distance of current node from root. 
    // 'hd' is initially passed as 0 
    static void getVerticalOrder(Node root, int hd, 
                                TreeMap<Integer,Vector<Integer>> m) 
    { 
        // Base case 
        if(root == null) 
            return; 
          
        //get the vector list at 'hd' 
        Vector<Integer> get =  m.get(hd); 
          
        // Store current node in map 'm' 
        if(get == null) 
        { 
            get = new Vector<>(); 
            get.add(root.key); 
        } 
        else
            get.add(root.key); 
          
        m.put(hd, get); 
          
        // Store nodes in left subtree 
        getVerticalOrder(root.left, hd-1, m); 
          
        // Store nodes in right subtree 
        getVerticalOrder(root.right, hd+1, m); 
    } 
      
    // The main function to print vertical oder of a binary tree 
    // with given root 
    static void printVerticalOrder(Node root) 
    { 
        // Create a map and store vertical oder in map using 
        // function getVerticalOrder() 
        TreeMap<Integer,Vector<Integer>> m = new TreeMap<>(); 
        int hd =0; 
        getVerticalOrder(root,hd,m); 
          
        // Traverse the map and print nodes at every horigontal 
        // distance (hd) 
        for (Entry<Integer, Vector<Integer>> entry : m.entrySet()) 
        { 
            System.out.println(entry.getValue()); 
        } 
    }

static void print(Node n) {
		Deque<Node> stack = new ArrayDeque<>();
		while (n != null) {
			stack.push(n);
			n = n.l;
		}
		doStack(stack);
	}
	
	static void doStack(Deque<Node> stack) {
		if (stack.isEmpty()) {return;}
		Node prev = stack.pop();
		System.out.println(prev.v);
		while (!stack.isEmpty()) {
			Node n = stack.pop();
			System.out.println(n.v);
			print(prev.r);
			prev = n;
		}
		print(prev.r);
	}

6 is the root. the space didn't come along well.

in-order traversal

in-order traversal?

class Node:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None


def getcoldistance(root,horzdist,mydict):
    if not root:
        return None
    if horzdist in mydict:
        mydict[horzdist].append(root.val)
    else:
        mydict[horzdist] = [root.val]
    getcoldistance(root.left,horzdist-1,mydict)
    getcoldistance(root.right,horzdist+1,mydict)

def printvertdist(root):
    m = {}
    getcoldistance(root,0,m)
    for key in sorted(m):
        for val in m[key]:
            print(val,end='')


root =  Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.right = Node(8)
root.right.right.right = Node(9)

printvertdist(root)

using level order traversal and keeping a hash map to preserve the order

void printTree(TreeNode root){
Queue<Pair> q = new LinkedList<Pair>();

TreeMap<Integer,LinkedList<Integer>> map = new TreeMap<Integer,LinkedList<TreeNode>> ();
if(root==null){
return;
}
q.add(new Pair(root,0));
int hd =0;
addValue(map, 0, root.val)



while(q.size()>0){
Pair pair = (Pair)q.poll();
TreeNode temp = q.getTreeNode();
hd = q.getHd();
if(temp.left!=null){
q.add(new Pair(temp.left,hd-1));
addValue(map, hd-1, temp.val);
}
if(temp.right!=null){
q.add(new Pair(temp.right,hd+1));
addValue(map, hd+1, temp.val);
}
}

Iterator<Integer> itr = map.getKeySet();
while(itr.hasNext()){
int key = (Integer)itr.next();
LinkedList l = map.get(key);
while(l!=null){
System.out.print(l.val+" ");
l= l.next;
}
}
}

void addValue(map, int key, int val){
if(map.get(key)==null){
LinkedList<Integer> l = new LinkedList<Integer>();
l.add(root.val);
map.put(0,l);
} else{
LinkedList<Integer> l = (LinkedList<Integer>)map.get(key);
l.add(val);
}
}

class Pair {
TreeNode node;
int hd;
public Pair(TreeNode node,int hd){
this.node = node;
this.hd =hd;
}
}

Traverse Breadth-First to preserve order for nodes with the same horizontal distance. Horizontal distance is used to find nodes in the same column I.e. horizontal distance for nodes 4, 7 and 12 is 1.
/*
..............6
............/...\
...........9.....4
........../..\....\
.........5....1....6
..........\......../
...........0.... .7
.............\.......
..............11
................\
.................12
...................\
...................13
.....................\
......................14
*/

private void printInVerticalOrder(Node root) {
        if (root == null){
            return;
        }
        TreeMap<Integer, List<Integer>> hdToValues = collectHorizontalDistancesToValues(root);
        print(hdToValues);
    }

    private TreeMap<Integer, List<Integer>> collectHorizontalDistancesToValues(Node root) {
        TreeMap<Integer, List<Integer>> hdToValues = new TreeMap<>();

        LinkedList<HDNode> nodes = new LinkedList<>();
        nodes.add(new HDNode(0, root));
        while (!nodes.isEmpty()) {
            HDNode hdNode = nodes.removeFirst();

            hdToValues.putIfAbsent(hdNode.hd, new ArrayList<>());
            hdToValues.get(hdNode.hd).add(hdNode.node.value);

            if(hdNode.node.left != null){
                nodes.add(new HDNode(hdNode.hd - 1, hdNode.node.left));
            }
            if(hdNode.node.right != null){
                nodes.add(new HDNode(hdNode.hd + 1, hdNode.node.right));
            }
        }
        return hdToValues;
    }

    private void print(TreeMap<Integer, List<Integer>> hdToValues) {
        while (!hdToValues.isEmpty()) {
            Map.Entry<Integer, List<Integer>> entry = hdToValues.pollFirstEntry();
            entry.getValue().forEach(v -> System.out.print(v + " "));
            System.out.println("\n");
        }
    }

    private class HDNode {
        int hd;
        Node node;

        HDNode(int hd, Node node) {
            this.hd = hd;
            this.node = node;
        }
    }

Class Data {
	public int nodeVal;
	public int dist;

	public Data(int n, int d) { nodeVal = n; dist = d;}
}

void stupidTreePrint(Node root) {
	List<Data> arr = new ArrayList<>();
	auxFunc(root, 0, arr);

	// stable sort
	Collection.sort(arr, (o1, o2) -> Integer.signum(o1.dist-o2.dist));

	arr.foreach(e -> System.out.println(" " + e.nodeval + " "));
}

void auxFunc(Node root, int dist, List<Data> arr) {
	if(root == null) return;

	Data tmp = new Data(root.value, dist);
	arr.add(tmp);

	auxFunc(root.left, dist - 1, arr);
	auxFunc(root.right, dist + 1, arr);
}

python implementation
/*
..............6
............/...\
...........9.....4
........../..\....\
.........5....1....6
..........\......../
...........0.... .7
.............\.......
..............11
................\
.................12
...................\
...................13
.....................\
......................14
*/

class Node:
    def __init__(self, val:int, left=None, right=None):
        self.val,self.left,self.right = val,left,right
    def __repr__(self): return f'{self.val}'

def mark_nodes(root, index, depth, res):
    cut = None
    if root.left is not None:
        mark_nodes(root.left, index-1, depth+1, res)
    res.append((root, index, depth))
    if root.right is not None:
        mark_nodes(root.right, index+1, depth+1, res)

def print_lrtd(sorted_nodes):
    accum = []
    mark_nodes(root, 0, 0, accum)
    sorted_nodes = sorted(accum, key=lambda x: (x[1],x[2]))
    return [i[0] for i in sorted_nodes]


Output:
stem = Node(0, None, Node(11, None, Node(12, None, Node(13, None, Node(14)))))
root = Node(6, Node(9, Node(5, None, stem), Node(1)), Node(4, None, Node(3, Node(7))))
print_lrtd(root)

Algorithm:
- Do a inorder tree traversal with following changes
Root Node is denoted with Row Ordinal and Column Ordinal as 0
Every time traversal take a left, Column Ordinal is decremented by 1
Every time traversal take a right, Column Ordinal is incremented by 1
Every time traversal takes to children, Row Ordinal is incremented by 1
Every time traversal moves back to parent, Row Ordinal is decremented by 1
- Sort Nodes based on Column Ordinal, if Column Ordinal matches, then use Row Ordinal
- Print Sorted Nodes

Psuedo-Code:

- Class Node definition is (Value, Left, Right)
- Class NodeEx definition is (Value, RowOrdinal, ColumnOrdinal)

class TreePrinter {
  private Node treeRootNode; 
  private ArrayList<NodeEx> nodes; 
  
  public TreePrinter(Node rootNode) {
    this.treeRootNode = rootNode;
    this.nodes = new ArrayList<NodeEx>();
  }
  
  public void printTree() {
    this.nodes.clear();
    traverseInOrder(rootNode, 0, 0);
    sortNodesByOrdinals();
    printNodes();
  }
  
  private void traverseInOrder(Node node, int rowOrdinal, int columnOrdinal) {
    if (null == node) return;
    this.nodes.append(new NodeEx(node.value, rowOrdinal, columnOrdinal));    
    traverseInOrder(node.Left, rowOrdinal+1, columnOrdinal-1);
    traverseInOrder(node.Right, rowOrdinal+1, columnOrdinal+1);
  }
  
  private sortNodesByOrdinals() {
    nodes.sort_by(node1, node2) {
      if node1.ColumnOrdinal < node2.ColumnOrdinal return -1;
      else node1.ColumnOrdinal > node2.ColumnOrdinal return +1;
      else if node1.RowOrdinal < node2.RowOrdinal return -1;
      else if node1.RowOrdinal > node2.RowOrdinal return +1;
      else return 0;
    }
  }
}

public class ByColumnTree {

  public static void main(String[] args) {

    Node root = root(6);
    Node n9 = root.left(9);
    n9.left(5).right(0);
    n9.right(1);
    root.right(4).right(3).left(7);

    List<Node> fringe = new LinkedList<>();

    traverse(fringe, root);
    
    Collections.sort(fringe);
    System.out.println(fringe);
  }

  private static void traverse(List<Node> fringe, Node node) {
    fringe.add(node);
    if(node.left != null) traverse(fringe, node.left);
    if(node.right !=  null) traverse(fringe, node.right);
  }

  static class Node implements Comparable<Node> {
    Node left;
    Node right;
    int val;

    int displacement;
    int depth;
    Node parent;

    static Node root(int val) {
      var node = new Node();
      node.val = val;
      return node;
    }

    Node left(int val) {
      var node = new Node();
      node.val = val;
      node.depth = this.depth + 1;
      node.displacement = this.displacement + 1;
      node.parent = this;
      this.left = node;
      return node;
    }

    Node right(int val) {
      var node = new Node();
      node.val = val;
      node.depth = this.depth + 1;
      node.displacement = this.displacement - 1;
      node.parent = this;
      this.right = node;
      return node;
    }

    @Override
    public int compareTo(Node other) {
      int d = Integer.compare(other.displacement, this.displacement);
      if (d != 0) return d;
      return Integer.compare(this.depth, other.depth);
    }

    @Override
    public String toString() {
      return String.valueOf(val);
    }
  }
}