Binary TreesProblem 11 of 35

Top View of a tree

Brute Force
Time: O(n log n)
Space: O(n)
Optimal
Time: O(n)
Space: O(n)

Problem Statement

Given a binary tree, print the top view of the tree. The top view is the set of nodes visible when the tree is viewed from the top. A node is in the top view if it is the first node at its horizontal distance from the root.

Example:

1 / \ 2 3 / \ \ 4 5 6
  • Input: Root of the above tree
  • Output: [4, 2, 1, 3, 6]

Horizontal distances: 4(-2), 2(-1), 1(0), 3(1), 6(2)

Approach 1: Using Map and Level Order Traversal

Intuition

Use horizontal distance (HD) concept. Root has HD=0, left child has HD-1, right child has HD+1. For top view, we want the first node at each HD (topmost).

Algorithm

  1. Perform level order traversal
  2. Track horizontal distance for each node
  3. Store first node seen at each HD in a map
  4. Return nodes sorted by HD
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<Integer> topView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        // TreeMap: horizontal distance -> first node value (auto-sorted by HD)
        TreeMap<Integer, Integer> hdMap = new TreeMap<>();
        
        // Queue: [node, horizontal distance]
        Queue<Object[]> queue = new LinkedList<>();
        queue.offer(new Object[]{root, 0});
        
        while (!queue.isEmpty()) {
            Object[] pair = queue.poll();
            TreeNode node = (TreeNode) pair[0];
            int hd = (int) pair[1];
            
            // Only add if this HD hasn't been seen
            if (!hdMap.containsKey(hd)) {
                hdMap.put(hd, node.val);
            }
            
            if (node.left != null) {
                queue.offer(new Object[]{node.left, hd - 1});
            }
            if (node.right != null) {
                queue.offer(new Object[]{node.right, hd + 1});
            }
        }
        
        // Extract values (already sorted by HD in TreeMap)
        result.addAll(hdMap.values());
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n log n) - Due to sorting by horizontal distance in map
  • Space Complexity: O(n) - Queue and map storage

Approach 2: Optimal (Using Array with Offset)

Intuition

If we know the range of horizontal distances, we can use an array instead of a map, avoiding the log factor from map operations.

Algorithm

  1. First pass: Find min and max horizontal distances
  2. Create array of size (max - min + 1)
  3. Second pass: Fill first occurrence at each HD
  4. Array indices directly give sorted order
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private int[] findHDRange(TreeNode root) {
        if (root == null) return new int[]{0, 0};
        
        int minHD = 0, maxHD = 0;
        Queue<Object[]> queue = new LinkedList<>();
        queue.offer(new Object[]{root, 0});
        
        while (!queue.isEmpty()) {
            Object[] pair = queue.poll();
            TreeNode node = (TreeNode) pair[0];
            int hd = (int) pair[1];
            
            minHD = Math.min(minHD, hd);
            maxHD = Math.max(maxHD, hd);
            
            if (node.left != null) queue.offer(new Object[]{node.left, hd - 1});
            if (node.right != null) queue.offer(new Object[]{node.right, hd + 1});
        }
        
        return new int[]{minHD, maxHD};
    }
    
    public List<Integer> topViewOptimal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        int[] range = findHDRange(root);
        int minHD = range[0], maxHD = range[1];
        int offset = -minHD;
        int size = maxHD - minHD + 1;
        
        Integer[] arr = new Integer[size];
        
        Queue<Object[]> queue = new LinkedList<>();
        queue.offer(new Object[]{root, 0});
        
        while (!queue.isEmpty()) {
            Object[] pair = queue.poll();
            TreeNode node = (TreeNode) pair[0];
            int hd = (int) pair[1];
            
            int idx = hd + offset;
            if (arr[idx] == null) {
                arr[idx] = node.val;
            }
            
            if (node.left != null) queue.offer(new Object[]{node.left, hd - 1});
            if (node.right != null) queue.offer(new Object[]{node.right, hd + 1});
        }
        
        for (Integer val : arr) {
            result.add(val);
        }
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Two passes, each O(n)
  • Space Complexity: O(n) - Queue and result array

Key Takeaways

  1. Horizontal Distance (HD) is key concept for top/bottom view problems
  2. Top view = first node at each horizontal distance (BFS ensures topmost)
  3. Use BFS to ensure level-by-level processing (topmost first)
  4. Map gives O(n log n) due to ordering, array with offset gives O(n)
  5. Similar concept applies to bottom view (last node at each HD)
  6. TreeMap in Java automatically sorts by key - useful for this problem
Previous
Right View of Tree
Next
Bottom View of a tree