top view java

// http://code2begin.blogspot.com
// program to print top view of binary tree

/**
 * Created by MOHIT on 25-05-2018.
 */

import java.io.*;
import java.util.*;

import static java.lang.Integer.max;


// node class
class node{
    int data;
    int hd;
    node left;
    node right;

    // function that returns a pointer to new node
    public node(int element){
        this.data = element;
        this.hd = -1;
        this.left = null;
        this.right = null;

    }
};


public class BinaryTree {

    // function to print the top view of the binary tree
    static void top_view(node root){
        if(root == null){
            return;
        }

        // we keep track of the horizontal distance of the node from the root node
        // to print the bottom view
        int hd = 0; // hd = horizontal distance from the root node
        hd = root.hd;

        // creating a Queue for storing node for level wise traversal
        // and a map for mapping horizontal distances with the node data
        ArrayList Q = new ArrayList<node>();;
        Map M = new HashMap<Integer, Integer>();

        Q.add(root);
        while(!Q.isEmpty()){

            // pop the first node from the queue
            node p = (node) Q.get(0);
            Q.remove(0);

            hd = p.hd;

            // if a horizontal distance is already mapped with a value then
            // we don't replace it with a new value
            if(!M.containsKey(hd)) {
                M.put(hd, p.data);
            }

            // increase the horizontal distance from the root node in negative direction
            // and push the node on queue
            if(p.left != null){
                p.left.hd = hd - 1;
                Q.add(p.left);
            }

            // increase the horizontal distance from the root node in positive direction
            // and push the node on queue
            if(p.right != null){
                p.right.hd = hd + 1;
                Q.add(p.right);
            }
        }

        // print the generated map
        System.out.print("\n\nTop view of the binary tree is : ");
        System.out.print(M.values());
    }


    public static void main(String arg[]) {
        node head = new node(1);
        head.left = new node(2);
        head.right = new node(3);
        head.left.left = new node(4);
        head.left.right = new node(5);
        head.right.right = new node(6);
        head.left.left.right = new node(7);
        head.right.right.left = new node(8);
        head.left.left.right.left = new node(9);
        head.left.left.right.left.left = new node(10);
        head.right.right.left.right = new node(11);
        head.hd = 0;

        System.out.print("Top view of the binary tree is : ");
        top_view(head);

    }
}