Print Nodes in Top View of Binary Tree - GeeksforGeeks

Print Nodes in Top View of Binary Tree - GeeksforGeeks
Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Given a binary tree, print the top view of it. The output nodes can be printed in any order. Expected time complexity is O(n)
A node x is there in output if x is the topmost node at its horizontal distance. Horizontal distance of left child of a node x is equal to horizontal distance of x minus 1, and that of right child is horizontal distance of x plus 1.

// 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));

        }

    }

}

http://www.ideserve.co.in/learn/top-view-of-a-binary-tree-using-level-order-traversal

    class TreeNode

    {

        TreeNode left;

        TreeNode right;

        int val;

     

        public TreeNode(int x)

        {

            this.val = x;

        }

    }

    TreeNode root;

    class QueueEntry

    {

        TreeNode node;

        int horizontalDistFromRoot;

        public QueueEntry (TreeNode node, int distance)

        {

            this.node = node;

            this.horizontalDistFromRoot = distance;

        }

    }

    private void fillUpViewMap(TreeNode root, Map viewMap)

    {

        if (root == null) return;

         

        LinkedList<QueueEntry> queue = new LinkedList();

        queue.add(new QueueEntry(root, 0));

         

        while (!queue.isEmpty())

        {

            QueueEntry currentNode = queue.remove();

            Integer mapEntry = (Integer)viewMap.get(currentNode.horizontalDistFromRoot);

             

            // if node exists in viewMap at this same horizontal distance

            // then we cannot add this node into viewMap.

            if (mapEntry == null)

            {

                viewMap.put(currentNode.horizontalDistFromRoot, currentNode.node.val);

            }

             

            // We don't add null nodes into the queue

            if (currentNode.node.left != null)

                queue.add(new QueueEntry(currentNode.node.left, currentNode.horizontalDistFromRoot - 1));

 

            if (currentNode.node.right != null)

                queue.add(new QueueEntry(currentNode.node.right, currentNode.horizontalDistFromRoot + 1));

        }

    }

    private void printTopView()

    {

        Map<Integer, Integer> viewMap = new TreeMap<>();

 

        fillUpViewMap(root, viewMap);

 

        // print map entries to print the top view

        Iterator<Entry<Integer, Integer>> iterator = viewMap.entrySet().iterator();

 

        while (iterator.hasNext())

        {

            Entry<Integer, Integer> nodeEntry = iterator.next();

            System.out.print("  " + nodeEntry.getValue());

        }

    }

http://algorithms.tutorialhorizon.com/print-the-top-view-of-a-binary-tree/
Read full article from Print Nodes in Top View of Binary Tree - GeeksforGeeks