medium Top View Of the Binary Tree

Problem Statement

Given a root of the binary tree, return an array containing nodes in its top view.

The top view of a binary tree consists of nodes that are visible when the tree is viewed from the top. If multiple nodes share the same horizontal distance from the root, only the first node encountered at that distance (in level order) is part of the top view.

Examples

Example 1

• Input: root = [1, 2, 3, null, 5, 4, 6]
• Expected Output: [2, 1, 3, 6]

• Justification: It is a top view of the tree as shown in the diagram.

Example 2

• Input: root = [1, 2, 3, 4, null, null, 7, 5, null, null, 8]
• Expected Output: [5, 4, 2, 1, 3, 7, 8]

• Justification: It is a top view of the tree as shown in the diagram.

Example 3

• Input: root = [1, null, 2, 3, null, null, 4]
• Expected Output: [1, 2]

• Justification: It is a top view of the tree as shown in the diagram.

Solution

To solve this problem, we can use the Breadth-First Search (BFS) approach. This method explores each level of the tree and ensures that the first node encountered at each horizontal distance is captured. We maintain a horizontal distance for each node starting from the root (horizontal distance = 0) and update the view with the first node encountered at each distance.

This approach is efficient because BFS ensures that we process nodes level by level, and we can keep track of horizontal distances using a queue. Since we're only interested in the first node we encounter at each horizontal distance, BFS works perfectly for this case. We also maintain a hash map to store the top view nodes for each horizontal distance.

Step-by-step Algorithm

1. Check if the tree is empty:

   • If the root is null, return an empty list since no top view is possible.

2. Create necessary data structures:

   • Initialize an empty list topViewNodes to store the result.
   • Use a TreeMap called topNodeMap to store the first node encountered at each horizontal distance. The key is the horizontal distance, and the value is the node value.
   • Use a Queue to perform Breadth-First Search (BFS). The queue will store pairs of nodes and their respective horizontal distance from the root.

3. Add the root node to the queue:

   • Insert the root node into the queue with a horizontal distance of 0.

4. Start BFS traversal:

   • While the queue is not empty, repeat steps 5 to 9:

5. Dequeue a node from the queue:

   • Remove a node from the queue along with its horizontal distance.

6. Check if the horizontal distance is already in the map:

   • If this horizontal distance is not in topNodeMap, insert the current node’s value into the map with its horizontal distance as the key.
   • This ensures only the first node encountered at this horizontal distance is stored, as we are processing the tree level by level.

7. Check if the current node has a left child:

   • If the node has a left child, enqueue the left child with a horizontal distance of current horizontal distance - 1.

8. Check if the current node has a right child:

   • If the node has a right child, enqueue the right child with a horizontal distance of current horizontal distance + 1.

9. Repeat the BFS traversal for all nodes:

   • Continue until all nodes are processed in the BFS loop.

10. Extract the results:

    • After the BFS completes, the topNodeMap contains the first node encountered at each horizontal distance. Since TreeMap stores the keys in sorted order, iterate through the entries in topNodeMap and add the node values to topViewNodes.

11. Return the result:

    • Return the list topViewNodes containing the top view of the binary tree.

Algorithm Walkthrough

Input: [1, 2, 3, null, 5, 4, 6]

1. Initial Setup:

   • topViewNodes = [] (empty list).
   • topNodeMap = {} (empty TreeMap).
   • queue = [(1, 0)] (root node 1 with horizontal distance 0).

2. First BFS iteration:

   • Dequeue (1, 0): current node is 1, horizontal distance is 0.
   • Since horizontal distance 0 is not in topNodeMap, add 1 to the map: topNodeMap = {0: 1}.
   • Enqueue the left child 2 with horizontal distance -1: queue = [(2, -1)].
   • Enqueue the right child 3 with horizontal distance 1: queue = [(2, -1), (3, 1)].

3. Second BFS iteration:

   • Dequeue (2, -1): current node is 2, horizontal distance is -1.
   • Since horizontal distance -1 is not in topNodeMap, add 2 to the map: topNodeMap = {-1: 2, 0: 1}.
   • Node 2 has no left child, so nothing is enqueued.
   • Enqueue the right child 5 with horizontal distance 0: queue = [(3, 1), (5, 0)].

4. Third BFS iteration:

   • Dequeue (3, 1): current node is 3, horizontal distance is 1.
   • Since horizontal distance 1 is not in topNodeMap, add 3 to the map: topNodeMap = {-1: 2, 0: 1, 1: 3}.
   • Enqueue the left child 4 with horizontal distance 0: queue = [(5, 0), (4, 0)].
   • Enqueue the right child 6 with horizontal distance 2: queue = [(5, 0), (4, 0), (6, 2)].

5. Fourth BFS iteration:

   • Dequeue (5, 0): current node is 5, horizontal distance is 0.
   • Since horizontal distance 0 is already in topNodeMap, we do not update the map (only the first node at each distance is kept).
   • Node 5 has no children, so nothing is enqueued.

6. Fifth BFS iteration:

   • Dequeue (4, 0): current node is 4, horizontal distance is 0.
   • Since horizontal distance 0 is already in topNodeMap, we do not update the map.
   • Node 4 has no children, so nothing is enqueued.

7. Sixth BFS iteration:

   • Dequeue (6, 2): current node is 6, horizontal distance is 2.
   • Since horizontal distance 2 is not in topNodeMap, add 6 to the map: topNodeMap = {-1: 2, 0: 1, 1: 3, 2: 6}.
   • Node 6 has no children, so nothing is enqueued.

8. BFS completed:

   • The queue is now empty, so we exit the BFS loop.

9. Extract the results:

   • Iterate through topNodeMap in order of horizontal distance: -1, 0, 1, 2.
   • Add the corresponding node values to topViewNodes: [2, 1, 3, 6].

10. Return the result:

• The final result is topViewNodes = [2, 1, 3, 6].

Code

import java.util.*;

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     TreeNode(int x) {
//         val = x;
//         left = null;
//         right = null;
//     }
// }

// Helper class to hold a node and its horizontal distance.
class Pair<K, V> {

  private K key;
  private V value;

  public Pair(K key, V value) {
    this.key = key;
    this.value = value;
  }

  public K getKey() {
    return key;
  }

  public V getValue() {
    return value;
  }
}

public class Solution {

  // Function to return the top view of the binary tree.
  public List<Integer> topView(TreeNode root) {
    // Result list to store the top view nodes.
    List<Integer> topViewNodes = new ArrayList<>();

    // If the tree is empty, return the empty result list.
    if (root == null) return topViewNodes;

    // Map to store the first node at each horizontal distance.
    Map<Integer, Integer> topNodeMap = new TreeMap<>();

    // Queue for level order traversal that holds pairs of nodes and their horizontal distance.
    Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();

    // Start with the root node at horizontal distance 0.
    queue.add(new Pair<>(root, 0));

    // BFS traversal loop
    while (!queue.isEmpty()) {
      // Extract the node and its horizontal distance from the queue.
      Pair<TreeNode, Integer> pair = queue.poll();
      TreeNode node = pair.getKey();
      int horizontalDistance = pair.getValue();

      // If this is the first node at this horizontal distance, add it to the map.
      if (!topNodeMap.containsKey(horizontalDistance)) {
        topNodeMap.put(horizontalDistance, node.val);
      }

      // If the node has a left child, enqueue it with horizontal distance - 1.
      if (node.left != null) {
        queue.add(new Pair<>(node.left, horizontalDistance - 1));
      }

      // If the node has a right child, enqueue it with horizontal distance + 1.
      if (node.right != null) {
        queue.add(new Pair<>(node.right, horizontalDistance + 1));
      }
    }

    // Add all values from the map to the result list, in sorted order of horizontal distance.
    for (Map.Entry<Integer, Integer> entry : topNodeMap.entrySet()) {
      topViewNodes.add(entry.getValue());
    }
    return topViewNodes;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    TreeNode root1 = new TreeNode(1);
    root1.left = new TreeNode(2);
    root1.right = new TreeNode(3);
    root1.left.right = new TreeNode(5);
    root1.right.left = new TreeNode(4);
    root1.right.right = new TreeNode(6);
    System.out.println(solution.topView(root1)); // Output: [2, 1, 3, 6]
  }
}

Complexity Analysis

Time Complexity

1. Level Order Traversal using Queue – :

• Every node in the tree is visited exactly once during the Breadth-First Search (BFS).
• For each node, we perform a constant amount of work (checking left/right children, calculating horizontal distance, etc.).
• So this part contributes

2. Storing values in TreeMap – per insertion:

• A TreeMap is used to keep nodes sorted by horizontal distance.
• Each put() or containsKey() operation in a TreeMap takes , where K is the number of keys in the map.
• In the worst case, you could have up to N different horizontal distances → so each insertion/check could take up to time.
• Over N nodes, the map operations cost in total.

3. Collecting and returning results – :

• After BFS, you collect values from the TreeMap, which takes .

Final Time Complexity:

• Queue traversal (BFS):
• TreeMap operations:
• Final result construction:

✅ So the overall time complexity is due to the use of TreeMap for sorting horizontal distances.

Space Complexity

• The space complexity of the algorithm is . This includes:
  • The queue used for BFS traversal, which in the worst case can contain nodes.
  • The TreeMap that stores nodes at different horizontal distances. In the worst case, the tree can be completely skewed, which means the number of unique horizontal distances will also be .