HackerRankSolutions/TreeTopView.java at master · Pradyuman7/HackerRankSolutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.util.*;
import java.io.*;

class Node {
    Node left;
    Node right;
    int data;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {

	/*

    class Node
    	int data;
    	Node left;
    	Node right;
	*/

	public static void topView(Node root) {
        class QueueObj {
            Node node;
            int hd;

            QueueObj(Node node, int hd) {
                this.node = node;
                this.hd = hd;
            }
        }

        Queue<QueueObj> q = new LinkedList<QueueObj>();
        Map<Integer, Node> topViewMap = new TreeMap<Integer, Node>();
        if (root == null)
            return;
        else
            q.add(new QueueObj(root, 0));

        while (!q.isEmpty()) {
            QueueObj tmpNode = q.poll();
            if (!topViewMap.containsKey(tmpNode.hd))
                topViewMap.put(tmpNode.hd, tmpNode.node);


            if (tmpNode.node.left != null)
                q.add(new QueueObj(tmpNode.node.left, tmpNode.hd - 1));

            if (tmpNode.node.right != null)
                q.add(new QueueObj(tmpNode.node.right, tmpNode.hd + 1));


        }
        for (Map.Entry<Integer, Node> entry : topViewMap.entrySet())
            System.out.print(entry.getValue().data+" ");


    }

	public static Node insert(Node root, int data) {