• # BinaryTree VerticalOrder Traversal in JAVA

This is my implementation of the BinaryTree vertical order traversal. Vertical order traversal is an algorithm that groups all nodes with the same horizontal distance together. Horizontal distance is the amount of divergence a node has compared to its parent. For example, suppose a node has horizontal distance of 0, then its left child will have horizontal distance of the current node's horizontal distance - 1 and its right child will have horizontal distance of the current node's horizontal distance + 1. I am using a LinkedHashMap that maps Integer of horizontal distance to List of nodes with that particular horizontal distance in the order of insertion. Lastly, I am using inorder traversal to ensure that the left subtree gets inserted into the map first.

### Implementation

``````public static void printVerticalOrder(TreeNode root) {
if (root == null) return;

Stack<TreeNode> parents = new Stack<TreeNode>();
Map<Integer, List<Integer>> map = new LinkedHashMap<Integer, List<Integer>>();

TreeNode cur = root;
while (!parents.isEmpty() || cur != null) {
if (cur != null) {
if (cur.left != null)
cur.left.hd = cur.hd - 1;

if (cur.right != null)
cur.right.hd = cur.hd + 1;

parents.push(cur);
cur = cur.left;
}
else {
TreeNode parent = parents.pop();

if (!map.containsKey(parent.hd))
map.put(parent.hd, new ArrayList<Integer>());

cur = parent.right;
}
}

Iterator<Integer> keys = map.keySet().iterator();
while (keys.hasNext()) {
int key = keys.next();
List<Integer> list = map.get(key);

for (int i = 0; i < list.size(); i++) {
System.out.printf("%d ", list.get(i));
}

System.out.println();
}
}``````
• ## Check if Array is in BST PreOrder Form in JAVA

This is my recursive implementation of the algorithm that checks if a given Array is in BinarySearchTree PreOrder form. The idea behind this algorithm is to start with the ...

• ## BinaryTree Maximum Sum Path in JAVA

This is my implementation of the algorithm on finding the maximum sum path of a BinaryTree. The path does not have to start from the root node and does not have to end on a...

• ## BinaryTree InOrder Traversal in JAVA

This is my iterative and recursive implementation of the InOrder traversal method on a BinaryTree data structure. InOrder traversal is a form of depth first traversal, so I...

• ## InsertionSort in JAVA

Insertion sort is a simple comparison sorting algorithm that uses two pointers to reorder a set of unsorted numbers. Suppose there is a set of unsorted numbers. If the set ...

• ## Heap Implementation in JAVA

This is my Java implementation of the Heap data structure. The Heap data structure is also known as the PriorityQueue in the Java standard library. It is a binary tree that...