Print Top Viewof Tree Algorithm
The Print Top View of Tree Algorithm is an efficient method used to display the top view of a given binary tree. This algorithm is particularly useful for visualizing the tree's structure from a bird's eye view, by showing only the nodes that are visible from the top. The top view of a binary tree consists of the leftmost nodes of each level, followed by the rightmost nodes of each level, excluding the nodes that have already been included in the top view. To accomplish this, the algorithm utilizes a combination of depth-first traversal and a horizontal distance concept to keep track of nodes that should be displayed in the top view.
In order to implement the Print Top View of Tree Algorithm, a depth-first search traversal is performed, starting from the root node. As the nodes are visited, their horizontal distance from the root node is calculated and stored in a dictionary or a hash table, where the key is the horizontal distance and the value is the node's data. When visiting a node, if its horizontal distance is not already present in the dictionary, it is added, implying that the node is part of the top view. If the horizontal distance is already present, it means that the node is not in the top view, and it is skipped. After the traversal is complete, the dictionary contains the nodes that make up the top view of the tree. The final step is to print these nodes in sorted order of their horizontal distances, displaying the top view of the binary tree.
package DataStructures.Trees;// Java program to print top view of Binary tree
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
// Class for a tree node
class TreeNode {
// Members
int key;
TreeNode left, right;
// Constructor
public TreeNode(int key) {
this.key = key;
left = right = null;
}
}
// A class to represent a queue item. The queue is used to do Level
// order traversal. Every Queue item contains node and horizontal
// distance of node from root
class QItem {
TreeNode node;
int hd;
public QItem(TreeNode n, int h) {
node = n;
hd = h;
}
}
// Class for a Binary Tree
class Tree {
TreeNode root;
// Constructors
public Tree() {
root = null;
}
public Tree(TreeNode n) {
root = n;
}
// This method prints nodes in top view of binary tree
public void printTopView() {
// base case
if (root == null) {
return;
}
// Creates an empty hashset
HashSet<Integer> set = new HashSet<>();
// Create a queue and add root to it
Queue<QItem> Q = new LinkedList<QItem>();
Q.add(new QItem(root, 0)); // Horizontal distance of root is 0
// Standard BFS or level order traversal loop
while (!Q.isEmpty()) {
// Remove the front item and get its details
QItem qi = Q.remove();
int hd = qi.hd;
TreeNode n = qi.node;
// If this is the first node at its horizontal distance,
// then this node is in top view
if (!set.contains(hd)) {
set.add(hd);
System.out.print(n.key + " ");
}
// Enqueue left and right children of current node
if (n.left != null)
Q.add(new QItem(n.left, hd - 1));
if (n.right != null)
Q.add(new QItem(n.right, hd + 1));
}
}
}
// Driver class to test above methods
public class PrintTopViewofTree {
public static void main(String[] args) {
/* Create following Binary Tree
1
/ \
2 3
\
4
\
5
\
6*/
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(4);
root.left.right.right = new TreeNode(5);
root.left.right.right.right = new TreeNode(6);
Tree t = new Tree(root);
System.out.println("Following are nodes in top view of Binary Tree");
t.printTopView();
}
}