Problem

Given a binary tree, print it in Bottom View of it.

The horizontal distance of a binary tree node describes how far left or right the node will be when the tree is printed out.

More rigorously, we can define it as follows:

  • The horizontal distance of the root is 0.
  • The horizontal distance of a left child is hd(parent) - 1.
  • The horizontal distance of a right child is hd(parent) + 1.

For example, for the following tree, hd(1) = -2, and hd(6) = 0.

The bottom view of a tree, then, consists of the lowest node at each horizontal distance. If there are two nodes at the same depth and horizontal distance, either is acceptable.

What is Bottom View?

Bottom view means when you look the tree from the bottom the nodes you will see will be called the bottom view of the tree.

Examples

Example 1: 

1
2

Input: root = [1,2,3,4,5,6,7]
Output: [4, 2, 6, 3, 7]

Solution

This problem is quite similar to the -

Just modified the code so that it will print only the last element it will encounter in the vertical order. That will be the bottom view.

How will you know that you are visiting the last node at every level(Vertically)?

  • Take a variable called level, whenever you go left, do level++ AND whenever you go right do level–. By level we mean here horizontal differential OR HD.
  • With step above we have separated out the levels vertically.

In top view, we care about the first element added to hashmap, but in bottom view we consider till the last element added for that distance.

Method 1 - Iterative BFS

To get the bottom view of a binary tree, we use a level order traversal (Breadth-First Search) while keeping track of horizontal distances of nodes in a dictionary. Each level’s elements are stored in the dictionary with the key as the horizontal distance and value as the node at that level. We iterate through the TreeMap at the end to print the bottom view.

Approach

  1. Initialize Data Structures: Start with initializing a queue and a dictionary (Map) where each key-value pair will be (horizontal distance, node value).
  2. Breadth-First Search: Implement a level order traversal (BFS) with a queue, keeping track of horizontal distances.
  3. Track Nodes: Store only the most recently visited node at each horizontal distance (i.e., the last node at each level).
  4. Result Extraction: After BFS traversal, extract the values in the dictionary in the order of their horizontal distances to form the bottom view.

See the code for better understanding.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

 class Solution {
    public List<Integer> bottomView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Map<Integer, Integer> hdNodeMap = new TreeMap<>();
        Queue<TreeNodeWithHd> queue = new LinkedList<>();
        queue.add(new TreeNodeWithHd(root, 0));

        while (!queue.isEmpty()) {
            TreeNodeWithHd nodeHd = queue.poll();
            TreeNode node = nodeHd.node;
            int hd = nodeHd.hd;

            hdNodeMap.put(hd, node.val);

            if (node.left != null) {
                queue.add(new TreeNodeWithHd(node.left, hd - 1));
            }

            if (node.right != null) {
                queue.add(new TreeNodeWithHd(node.right, hd + 1));
            }
        }

        for (Map.Entry<Integer, Integer> entry : hdNodeMap.entrySet()) {
            result.add(entry.getValue());
        }

        return result;
    }
}

class TreeNodeWithHd {
    TreeNode node;
    int hd;
    TreeNodeWithHd(TreeNode node, int hd) {
        this.node = node;
        this.hd = hd;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def bottomView(self, root: TreeNode) -> List[int]:
        if not root:
            return []

        hd_node_map = {}
        queue = deque([(root, 0)])

        while queue:
            node, hd = queue.popleft()
            hd_node_map[hd] = node.val

            if node.left:
                queue.append((node.left, hd - 1))
            
            if node.right:
                queue.append((node.right, hd + 1))
        
        return [hd_node_map[hd] for hd in sorted(hd_node_map)]

Complexity

  • ⏰ Time complexity: O(n) - where n is the number of nodes in the binary tree. Each node is visited once.
  • 🧺 Space complexity: O(n) - due to the storage of nodes in the queue and the dictionary.