Updated March 17, 2023
Definition
In Java, the vertical order traversal of a binary tree is a traversal algorithm that outputs the nodes in the vertical order of a binary tree. In this traversal, nodes at the same horizontal distance from the root node are clustered together and output their depth in ascending order. The vertical distance is defined as the distance from the root node to a node along a vertical line. The horizontal distance is defined as the distance between a node and the root node along a horizontal line, where the distance to the left of the root node is considered negative(-1), and the distance to the right of the root node is considered positive(+1). The nodes are output in ascending order of their values when multiple nodes have the same horizontal values.
Binary Tree Map
To accomplish this traversal, we can use a TreeMap to keep track of the nodes’ horizontal distances and recursively traverse the tree in pre-order.
Methods to Find Vertical Order Traversal of a Binary Tree in Java
Below given are the methods to find vertical order traversal.
1. Horizontal Distance (hashing)
When traversing a binary tree, the horizontal distance of a node is the distance from the root node, with the root having a distance of 0, its left child a distance of -1, and its right child a distance of +1. To achieve a vertical order traversal of the tree, we can utilize a hash table to organize nodes according to their horizontal distances. Starting at the root with a distance of 0, we traverse the tree recursively and store nodes in the hash table based on their distances. Then, we can traverse the hash table in a top-down order to obtain nodes in the correct grouping. This method enables us to explore nodes in the desired order and groups nodes with the same distance.
Code:
import java.util.*;
public class BinaryTreeVerticalTraversal {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public List<List<Integer>> verticalTraversal(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Map<Integer, List<Integer>> map = new TreeMap<>();
Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> dist = new LinkedList<>();
queue.offer(root);
dist.offer(0);
while (!queue.isEmpty()) {
int size = queue.size();
Map<Integer, List<Integer>> levelMap = new HashMap<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
int horizontalDist = dist.poll();
if (!levelMap.containsKey(horizontalDist)) {
levelMap.put(horizontalDist, new ArrayList<>());
}
levelMap.get(horizontalDist).add(node.val);
if (node.left != null) {
queue.offer(node.left);
dist.offer(horizontalDist - 1);
}
if (node.right != null) {
queue.offer(node.right);
dist.offer(horizontalDist + 1);
}
}
for (int key : levelMap.keySet()) {
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
List<Integer> values = levelMap.get(key);
Collections.sort(values);
map.get(key).addAll(values);
}
}
for (int key : map.keySet()) {
result.add(map.get(key));
}
return result;
}
public static void main(String[] args) {
/*
* 3
* / \
* 9 8
* / \
* 4 5
*/
TreeNode root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(8);
root.right.left = new TreeNode(4);
root.right.right = new TreeNode(5);
BinaryTreeVerticalTraversal btvt = new BinaryTreeVerticalTraversal();
List<List<Integer>> result = btvt.verticalTraversal(root);
for (List<Integer> list : result) {
for (int val : list) {
System.out.print(val + " ");
}
System.out.println();
}
}
}Output:
2. Level Order Traversal
When traversing a binary tree level by level, we visit all the nodes in a breadth-first search starting from the root node. To achieve a vertical order traversal using this approach, we can utilize a queue to keep track of the nodes in the correct order. During each iteration of the traversal, we dequeue the nodes from the queue and store them in a list based on their horizontal distance from the root node. We then enqueue each node’s left and right child in the queue and repeat this process until all nodes have been traversed. Finally, we output the nodes in each list from top to bottom, giving us the binary tree’s vertical order traversal. This method enables us to explore the tree in a breadth-first manner while organizing the nodes based on their horizontal distance.
Code:
import java.util.*;
public class BinaryTreeVerticalTraversal {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public List<List<Integer>> verticalTraversal(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Map<Integer, List<Integer>> map = new HashMap<>();
Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> dist = new LinkedList<>();
queue.offer(root);
dist.offer(0);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
int horizontalDist = dist.poll();
if (!map.containsKey(horizontalDist)) {
map.put(horizontalDist, new ArrayList<>());
}
map.get(horizontalDist).add(node.val);
if (node.left != null) {
queue.offer(node.left);
dist.offer(horizontalDist - 1);
}
if (node.right != null) {
queue.offer(node.right);
dist.offer(horizontalDist + 1);
}
}
}
int minDist = Collections.min(map.keySet());
int maxDist = Collections.max(map.keySet());
for (int i = minDist; i <= maxDist; i++) {
if (map.containsKey(i)) {
result.add(map.get(i));
}
}
return result;
}
public static void main(String[] args) {
/*
* 1
* / \
* 2 3
* / \ / \
* 4 5 6 7
*/
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
BinaryTreeVerticalTraversal btvt = new BinaryTreeVerticalTraversal();
List<List<Integer>> result = btvt.verticalTraversal(root);
for (List<Integer> list : result) {
for (int val : list) {
System.out.print(val + " ");
}
System.out.println();
}
}
}Output:
3. TreeMap
- Create a TreeMap<Integer, List<Integer>> to store the nodes based on their horizontal distance from the root node. The key represents the horizontal distance, and the value is a list of nodes at that distance.
- Create a helper method verticalOrderTraversalUtil that takes in the root node, the horizontal distance, and the TreeMap.
- In verticalOrderTraversalUtil, add the node value to the list corresponding to its horizontal distance in the TreeMap. If a list does not exist for the horizontal distance, create a new one.
- Recursively call verticalOrderTraversalUtil for the left and right subtrees with the updated horizontal distance. The horizontal distance for the left subtree is the current horizontal distance minus one, and the horizontal distance for the right subtree is the current horizontal distance plus one.
- Create the verticalOrderTraversal method that calls the verticalOrderTraversalUtil method with the root node, a horizontal distance of 0, and the empty TreeMap.
- Return the TreeMap from the vertical order traversal method.
- Finally, iterate over the keys of the TreeMap in ascending order and output the corresponding lists of nodes. This will give us the vertical order traversal of the binary tree.
Java code for the verticalOrderTraversalUtil method and the vertical order traversal method:
Code:
import java.util.Map.Entry;
import java.util.TreeMap;
import java.util.Vector;
public class VOBtree {
static class Node {
int key;
Node lft;
Node rht;
Node(int data)
{
key = data;
lft = null;
rht = null;
}
}
static void
getVerticalOrder(Node root, int hd,
TreeMap<Integer, Vector<Integer> > m)
{
// Base case
if (root == null)
return;
Vector<Integer> get = m.get(hd);
if (get == null) {
get = new Vector<>();
get.add(root.key);
}
else
get.add(root.key);
m.put(hd, get);
getVerticalOrder(root.lft, hd - 1, m);
getVerticalOrder(root.rht, hd + 1, m);
}
static void printVerticalOrder(Node root)
{
TreeMap<Integer, Vector<Integer> > m = new TreeMap<>();
int hd = 0;
getVerticalOrder(root, hd, m);
// Traverse the map and print nodes at every
// horizontal distance (hd)
for (Entry<Integer, Vector<Integer> > entry :
m.entrySet()) {
System.out.println(entry.getValue());
}
}
public static void main(String[] args)
{
Node root = new Node(11);
root.lft = new Node(23);
root.rht = new Node(34);
root.lft.lft = new Node(46);
root.lft.rht = new Node(53);
root.rht.lft = new Node(67);
root.rht.rht = new Node(72);
System.out.println("Vertical Order traversal is: ");
printVerticalOrder(root);
}
}Output:
Key Takeaways
- It allows us to print the nodes of the binary tree vertically, according to their horizontal distance from the root node.
- We can use various techniques such as TreeMap, hashing, or level order traversal to implement this traversal.
- The output is a list of lists or a vertical output of the nodes in the binary tree.
Conclusion
To sum up, vertical order traversal is a useful technique for analyzing the structure of binary trees. It helps to organize the nodes based on their horizontal distance from the root node and can be implemented in different ways, such as TreeMap, hashing, or level order traversal. This technique has various benefits, such as creating vertical histograms, determining a binary tree’s minimum and maximum widths, and offering a visual representation of the tree’s structure. By using vertical order traversal, we gain insights into the relationships between the nodes, making it an important tool for computer scientists and researchers.
Recommended Article
We hope that this EDUCBA information on “Vertical Order Traversal of a Binary Tree in Java” was beneficial to you. You can view EDUCBA’s recommended articles for more information.
