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();
    }
}

LANGUAGE:

DARK MODE: