How to Print the Top View of a Binary Tree Using Conditional Statements

How can I print the top view of a binary tree using two if statements?

// Sample implementation in Java
class Node {
    int data;
    Node left, right;

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

public void topView(Node root) {
    if (root == null) return;
    // Call to helper method would go here
}

The top view of a binary tree consists of the nodes that are visible when the tree is viewed from above. In order to print the top view, we can use a breadth-first search (BFS) approach while maintaining a record of nodes at each horizontal distance from the root. Here's how we can effectively implement this using two conditional statements.

import java.util.*;

class BinaryTree {
    Node root;

    public void topView() {
        if (root == null) return;
        Map<Integer, Integer> topViewMap = new TreeMap<>();
        Queue<Pair<Node, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>(root, 0));

        while (!queue.isEmpty()) {
            Pair<Node, Integer> current = queue.poll();
            Node currentNode = current.getKey();
            int horizontalDistance = current.getValue();

            // Using two if conditions to check and put in the map
            if (!topViewMap.containsKey(horizontalDistance)) {
                topViewMap.put(horizontalDistance, currentNode.data);
            }

            // Add left and right nodes to the queue
            if (currentNode.left != null) {
                queue.add(new Pair<>(currentNode.left, horizontalDistance - 1));
            }
            if (currentNode.right != null) {
                queue.add(new Pair<>(currentNode.right, horizontalDistance + 1));
            }
        }

        // Print the nodes in the top view
        for (Map.Entry<Integer, Integer> entry : topViewMap.entrySet()) {
            System.out.print(entry.getValue() + " ");
        }
    }
}

Causes

• Lack of understanding of tree traversal techniques.
• Improper handling of node visibility based on their horizontal position.
• Forgetting to account for duplicates in horizontal distances.

Solutions

• Utilize a HashMap to store the first node encountered at each horizontal distance.
• Use a Queue for level-order traversal while keeping track of horizontal distances with respect to the root.
• Implement two if statements to conditionally add nodes to the HashMap based on their horizontal distances.

Mistake: Not initializing the tree nodes properly.

Solution: Ensure that you create instances of Node and set up the tree structure correctly.

Mistake: Confusing horizontal distance calculations.

Solution: Remember that left children should decrease the horizontal distance and right children should increase it.

Mistake: Omitting cases for null nodes during tree traversal.

Solution: Always check for null before accessing node properties.