DSA 450 Notes

Problem Statement

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

Example:

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

Note: 5 and 6 are at HD=0 and HD=1 respectively at lower levels, so they appear in bottom view.

Approach 1: Using Map and Level Order Traversal

Intuition

Use horizontal distance (HD) concept. For bottom view, we want the last node at each HD (bottommost). BFS with continuous update ensures the last node at each HD is stored.

Algorithm

Perform level order traversal
Track horizontal distance for each node
Keep updating the node at each HD (last update wins)
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> bottomView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        // TreeMap: horizontal distance -> 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];
            
            // Always update - last node at this HD wins
            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 map operations and sorting
Space Complexity: O(n) - Queue and map storage

Approach 2: Optimal (Track Level with HD)

Intuition

Track both horizontal distance and level. Update the map only if the current node is at a deeper level than the previously stored node at that HD.

Algorithm

Store both value and level at each HD
Update only if current level >= stored level
This ensures the bottommost node is stored

java

import java.util.*;

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

public class Solution {
    public List<Integer> bottomViewWithLevel(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        // TreeMap: HD -> [value, level]
        TreeMap<Integer, int[]> hdMap = new TreeMap<>();
        
        // Queue: [node, HD, level]
        Queue<Object[]> queue = new LinkedList<>();
        queue.offer(new Object[]{root, 0, 0});
        
        while (!queue.isEmpty()) {
            Object[] data = queue.poll();
            TreeNode node = (TreeNode) data[0];
            int hd = (int) data[1];
            int level = (int) data[2];
            
            // Update if HD not seen or current level >= stored level
            if (!hdMap.containsKey(hd) || level >= hdMap.get(hd)[1]) {
                hdMap.put(hd, new int[]{node.val, level});
            }
            
            if (node.left != null) {
                queue.offer(new Object[]{node.left, hd - 1, level + 1});
            }
            if (node.right != null) {
                queue.offer(new Object[]{node.right, hd + 1, level + 1});
            }
        }
        
        // Extract values
        for (int[] pair : hdMap.values()) {
            result.add(pair[0]);
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n log n) - Map operations with sorting
Space Complexity: O(n) - Queue and map storage

Approach 3: DFS Alternative

Intuition

Use DFS with level tracking. For each HD, keep the node with the maximum level (bottommost).

Complexity Analysis

Time Complexity: O(n log n) - Map operations and sorting
Space Complexity: O(n) - Recursion stack and map

Key Takeaways

Bottom view = last node at each horizontal distance
Key difference from top view: Update map for every node (last update wins)
BFS naturally processes top-to-bottom, so last update is bottommost
For DFS, must track level to ensure bottommost node is selected
Use >= for level comparison to handle ties (rightmost at same level)
TreeMap in Java auto-sorts by HD, avoiding separate sort step

Bottom View of a tree

Problem Statement

Approach 1: Using Map and Level Order Traversal

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (Track Level with HD)

Intuition

Algorithm

Complexity Analysis

Approach 3: DFS Alternative

Intuition

Complexity Analysis

Key Takeaways