Print the Binary Tree in Vertical Order Path.

Objective: Given a binary tree, print it in vertical order path.

What is Vertical Order

Vertical Order Print Exampleas you can see in the example above, [4],[2], [1,5,6],[3],[7] are the verical order of the given binary tree.

Approach:

  • Its a tricky solution.
  • Do the preordertraversal.
  • Take a variable called level, when ever you go left, do level++ AND when ever you go right do level–.
  • With step above we have separated out the levels vertically.
  • Now you need to store the elements of each level, so create a TreeMap and the (key,value) pair will be (level,elements at that level).
  • At the end iterate through the TreeMap and print the results.
Separate out the vertical levels
Separate out the vertical levels

Complete Code:

import java.util.ArrayList;
import java.util.Set;
import java.util.TreeMap;
public class VerticalOrder {
public static TreeMap<Integer, ArrayList> ht = new TreeMap<>();
public ArrayList<Integer> al;
public void vertical(Node root, int level) {
if (root == null) {
return;
}
if (ht.containsKey(level)) {
ArrayList x = ht.get(level);
x.add(root.data);
ht.put(level, x);
} else {
al = new ArrayList<>();
al.add(root.data);
ht.put(level, al);
}
vertical(root.left, level1);
vertical(root.right, level+1);
}
public void printResult(TreeMap ht) {
Set<Integer> i = ht.keySet();
for (int keys : i) {
System.out.println(ht.get(keys));
}
}
public static void main(String args[]) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
VerticalOrder p = new VerticalOrder();
p.vertical(root, 0);
p.printResult(ht);
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}

view raw
VerticalOrder.java
hosted with ❤ by GitHub

Output:

[4]
[2]
[1, 5, 6]
[3]
[7]