We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Trees
  4. Tree : Top View
  5. Discussions

Tree : Top View

  • imjunqing
     + 0 comments

    Here's the Java code, I used the approach from geekstogeeks. I think the question did not specifiy and clearly define what a top view is. The correct implementation which passes all test cases should be according to this https://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/. 

    public static void topView(Node root) {
        Dictionary<Node, Integer> dictionary = new Hashtable<>();
        Map<Integer, Node> topResult = new TreeMap<>();
        Queue<Node> nodes = new LinkedList<>();

        if (root != null) {
            topResult.put(0, root);
            dictionary.put(root, 0);
            nodes.add(root);
        }

        while (!nodes.isEmpty()) {
            Node current = nodes.remove();
            int currentOrder = dictionary.get(current);

            if (current.left != null) {
                int value = currentOrder-1;

                if (!topResult.containsKey(value)) {
                    topResult.put(value, current.left);
                }
                dictionary.put(current.left, value);
                nodes.add(current.left);
            }

            if (current.right != null) {
                int value = currentOrder+1;

                if (!topResult.containsKey(value)) {
                    topResult.put(value, current.right);
                }
                dictionary.put(current.right, value);
                nodes.add(current.right);
            }
        }

        for (Node node : topResult.values()) {
            System.out.print(node.data + " ");
        }
    }