Bottom View of Binary Tree in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the bottom view of a binary tree?

The bottom view of a binary tree is the set of nodes visible when the tree is seen from the bottom. It shows the last node at each horizontal distance from the root.

beginner

How do we assign horizontal distances to nodes in a binary tree for bottom view?

We assign 0 to the root node. For the left child, horizontal distance is parent's distance minus 1. For the right child, it is parent's distance plus 1.

intermediate

Which data structure is commonly used to track nodes and their horizontal distances during bottom view traversal?

A queue is used for level order traversal, and a map (or dictionary) stores the latest node at each horizontal distance.

intermediate

Why does the bottom view use level order traversal instead of inorder or preorder?

Level order traversal visits nodes level by level, ensuring the bottom-most node at each horizontal distance is recorded last, which is needed for the bottom view.

intermediate

What is the output of bottom view for this tree?

20
/ \
8 22
/ \ \
5 3 25
/ \
10 14

The bottom view nodes are: 5 -> 10 -> 3 -> 14 -> 25

What horizontal distance is assigned to the root node in bottom view calculation?

A Depends on tree height

B 1

C 0

D -1

The root node is always assigned horizontal distance 0.

Which traversal method is best suited to find the bottom view of a binary tree?

A Level order traversal

B Inorder traversal

C Preorder traversal

D Postorder traversal

Level order traversal visits nodes level by level, capturing the bottom-most nodes last.

In bottom view, what happens if two nodes share the same horizontal distance and level?

A The node visited last in level order is chosen

B The right node is chosen

C The left node is chosen

D Both nodes are shown

The node visited last at that horizontal distance in level order traversal is recorded for bottom view.

What data structure helps store the latest node at each horizontal distance during bottom view calculation?

A Queue

B Map or dictionary

C Stack

D Linked list

A map or dictionary stores nodes keyed by their horizontal distance.

What is the bottom view output for a tree with only a root node?

A Empty

B Left child only

C Right child only

D Root node only

With only root, bottom view is just the root node.

Explain how to compute the bottom view of a binary tree step-by-step.

Think about horizontal distances and level order traversal.

Describe why level order traversal is important for bottom view compared to other traversals.

Consider how nodes are visited and overwritten.

Practice

1. What does the bottom view of a binary tree represent?

easy

A. Nodes visible when the tree is viewed from the bottom

B. Nodes visible when the tree is viewed from the top

C. Nodes visible when the tree is viewed from the left side

D. Nodes visible when the tree is viewed from the right side

Solution

1. Step 1: Understand the bottom view concept

   The bottom view shows nodes that are visible when looking at the tree from below, ignoring nodes hidden behind others.

2. Step 2: Compare with other views

   Top, left, and right views show nodes from different angles, but bottom view specifically shows the lowest nodes at each horizontal distance.

3. Final Answer:

   Nodes visible when the tree is viewed from the bottom -> Option A

4. Quick Check:

   Bottom view = nodes visible from below [OK]

Hint: Bottom view shows lowest nodes at each horizontal position [OK]

Common Mistakes:

• Confusing bottom view with top view
• Thinking it shows all leaf nodes only
• Mixing bottom view with side views

2. Which data structure is commonly used to track nodes and their horizontal distances for bottom view calculation?

easy

A. Stack

B. Hash Map (Dictionary)

C. Linked List

D. Queue

Solution

1. Step 1: Identify the need for horizontal distance mapping

   To find the bottom view, we map each node's horizontal distance to its value, updating with the lowest node at that distance.

2. Step 2: Choose the suitable data structure

   A hash map (dictionary) stores horizontal distance as key and node value as value, allowing quick updates and lookups.

3. Final Answer:

   Hash Map (Dictionary) -> Option B

4. Quick Check:

   Use hash map to map horizontal distance to node [OK]

Hint: Use hash map to store horizontal distance and node value [OK]

Common Mistakes:

• Using stack which is LIFO and not suitable here
• Using queue alone without mapping distances
• Using linked list which is inefficient for lookups

3. What is the bottom view output of this binary tree?

        1
       / \
      2   3
       \   \
        4   5
         \   \
          6   7

Options show node values from left to right in bottom view.

medium

A. [2, 4, 6, 7]

B. [2, 4, 6, 3, 7]

C. [2, 4, 6, 5, 7]

D. [1, 2, 4, 6, 7]

Solution

1. Step 1: Assign horizontal distances and track bottom nodes

   Assign horizontal distances: 1=0, 2=-1, 3=1, 4=0, 5=2, 6=1, 7=3. Bottom nodes at each distance are: -1:2, 0:4, 1:6, 2:5, 3:7.

2. Step 2: Collect bottom view nodes from left to right

   From leftmost (-1) to rightmost (3), nodes are 2, 4, 6, 5, 7.

3. Final Answer:

   [2, 4, 6, 5, 7] -> Option C

4. Quick Check:

   Bottom view nodes left to right = [2, 4, 6, 5, 7] [OK]

Hint: Track horizontal distances and pick last node at each [OK]

Common Mistakes:

• Including nodes not visible from bottom
• Confusing horizontal distances
• Listing nodes in wrong order

4. Identify the error in this C code snippet for bottom view calculation:

void bottomView(Node* root) {
    map hdNodeMap;
    queue> q;
    q.push({root, 0});
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        Node* node = p.first;
        int hd = p.second;
        if (hdNodeMap.find(hd) == hdNodeMap.end()) {
            hdNodeMap[hd] = node->data;
        }
        if (node->left) q.push({node->left, hd - 1});
        if (node->right) q.push({node->right, hd + 1});
    }
    for (auto it : hdNodeMap) {
        cout << it.second << " ";
    }
}

medium

A. Output loop should print keys instead of values

B. Queue is not initialized properly

C. Left and right child checks are reversed

D. Using map prevents updating bottom nodes at same horizontal distance

Solution

1. Step 1: Analyze map usage for horizontal distances

   The code inserts node data only if horizontal distance is not present, so it keeps the first node seen, which is top view behavior.

2. Step 2: Correct approach for bottom view

   For bottom view, update the map every time a node at the same horizontal distance is found, so the last node at that distance remains.

3. Final Answer:

   Using map prevents updating bottom nodes at same horizontal distance -> Option D

4. Quick Check:

   Bottom view needs updating map entries [OK]

Hint: Update map for every node at horizontal distance for bottom view [OK]

Common Mistakes:

• Using if condition to insert only once (top view logic)
• Not updating map with lower nodes
• Confusing top and bottom view logic

5. Given a binary tree where multiple nodes share the same horizontal distance and level, how should the bottom view algorithm decide which node to show?

hard

A. Show the node that appears last in level order traversal at that horizontal distance

B. Show the node that appears first in level order traversal at that horizontal distance

C. Show the node with the smallest value at that horizontal distance

D. Show the node with the largest value at that horizontal distance

Solution

1. Step 1: Understand node conflicts at same horizontal distance and level

   When nodes share horizontal distance and level, bottom view shows the one visible from bottom, which is the last node encountered in level order at that position.

2. Step 2: Use level order traversal order to decide

   Level order traversal visits nodes top to bottom, left to right. The last node at a horizontal distance overwrites previous ones in the map.

3. Final Answer:

   Show the node that appears last in level order traversal at that horizontal distance -> Option A

4. Quick Check:

   Bottom view picks last node at horizontal distance [OK]

Hint: Last node at horizontal distance in level order is bottom view node [OK]

Common Mistakes:

• Picking first node instead of last
• Choosing node by value instead of position
• Ignoring traversal order impact