Bottom View of Binary Tree in DSA Go - 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?

The root node is assigned horizontal distance 0. Left child nodes get horizontal distance -1 from their parent, right child nodes get +1. This helps track nodes vertically.

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 (dictionary) stores the latest node at each horizontal distance.

intermediate

Why does the bottom view keep updating the node at a horizontal distance during traversal?

Because nodes at lower levels overwrite nodes at the same horizontal distance seen earlier, ensuring the bottom-most node is recorded.

intermediate

What is the time complexity of finding the bottom view of a binary tree?

The time complexity is O(n), where n is the number of nodes, because each node is visited once during level order traversal.

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

A 1

B 0

C -1

D Depends on tree height

The root node is always assigned horizontal distance 0.

Which traversal method is best suited for computing the bottom view?

A Level order traversal

B Preorder traversal

C Inorder traversal

D Postorder traversal

Level order traversal visits nodes level by level, which helps update bottom view nodes correctly.

In bottom view, if two nodes share the same horizontal distance, which one is visible?

A The node at higher level

B The right node

C The node at lower level

D The left node

The node at the lower level (closer to bottom) is visible in bottom view.

What data structure stores the latest node at each horizontal distance during bottom view computation?

A Stack

B Linked List

C Queue

D Map/Dictionary

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

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

A Root node only

B Empty

C Left child only

D Right child only

With only root node, 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 preferred over inorder or preorder for bottom view.

Consider how nodes at same horizontal distance but different levels are handled.

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 view shows nodes from above, left view from left side, right view from right side. Bottom view is unique for the bottom perspective.

3. Final Answer:

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

4. Quick Check:

   Bottom view = Nodes visible from bottom [OK]

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

Common Mistakes:

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

2. Which data structure is commonly used to track nodes and their horizontal distances when computing the bottom view of a binary tree in Go?

easy

A. Stack

B. Queue

C. Map (dictionary)

D. Slice

Solution

1. Step 1: Identify the need to map horizontal distances

   To find bottom view, we track nodes by their horizontal distance from root, so we need a structure to map distance to node value.

2. Step 2: Choose the correct data structure

   A map (dictionary) stores key-value pairs, perfect for horizontal distance as key and node value as value.

3. Final Answer:

   Map (dictionary) -> Option C

4. Quick Check:

   Use map to store horizontal distance -> node [OK]

Hint: Use map to link horizontal distance with node value [OK]

Common Mistakes:

• Using stack which is LIFO, not suitable here
• Using queue only for traversal, not for mapping
• Using slice without keys for horizontal distance

3. Given the binary tree below, what is the bottom view output?

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

medium

A. [8, 10, 3, 14, 25]

B. [5, 10, 3, 14, 25]

C. [5, 10, 3, 22, 25]

D. [5, 8, 10, 14, 25]

Solution

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

   Assign horizontal distances (HD) starting from root (20) as 0. Left child decreases HD by 1, right child increases by 1. - 20 (HD=0) - 8 (HD=-1), 22 (HD=1) - 5 (HD=-2), 3 (HD=0), 25 (HD=2) - 10 (HD=-1), 14 (HD=1)

2. Step 2: Determine bottom view nodes by last node at each HD

   At HD=-2: 5 HD=-1: 10 (overwrites 8) HD=0: 3 (overwrites 20) HD=1: 14 (overwrites 22) HD=2: 25 Bottom view = [5, 10, 3, 14, 25]

3. Final Answer:

   [5, 10, 3, 14, 25] -> Option B

4. Quick Check:

   Bottom view nodes by HD = [5,10,3,14,25] [OK]

Hint: Track last node at each horizontal distance [OK]

Common Mistakes:

• Taking first node at HD instead of last
• Mixing horizontal distances
• Ignoring nodes on right side

4. Consider this Go code snippet for bottom view. What is the error?

func bottomView(root *Node) []int {
    if root == nil {
        return nil
    }
    queue := []*Node{root}
    hdMap := make(map[int]int)
    hd := 0
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        hdMap[hd] = node.val
        if node.left != nil {
            queue = append(queue, node.left)
            hd--
        }
        if node.right != nil {
            queue = append(queue, node.right)
            hd++
        }
    }
    // code to extract and return bottom view omitted
    return nil
}

medium

A. Queue is not initialized properly

B. Function returns nil instead of bottom view slice

C. Map is declared with wrong type

D. Horizontal distance (hd) is not tracked per node, causing wrong mapping

Solution

1. Step 1: Analyze horizontal distance tracking

   The variable hd is a single integer updated globally, but each node can have different hd. It should be tracked per node, e.g., by storing node and hd together in queue.

2. Step 2: Identify impact of error

   Because hd is not per node, hdMap updates will be incorrect, leading to wrong bottom view.

3. Final Answer:

   Horizontal distance (hd) is not tracked per node, causing wrong mapping -> Option D

4. Quick Check:

   Track hd per node, not globally [OK]

Hint: Track horizontal distance with each node in queue [OK]

Common Mistakes:

• Updating hd globally instead of per node
• Ignoring nil root check
• Returning nil without result

5. You want to print the bottom view of a binary tree but only for nodes with horizontal distance between -1 and 1 inclusive. How would you modify the standard bottom view algorithm to achieve this?

hard

A. Store all nodes in map, then filter keys between -1 and 1 before printing

B. Ignore nodes outside horizontal distance range during traversal

C. Use a stack instead of queue for traversal

D. Traverse tree in preorder and print nodes with hd between -1 and 1

Solution

1. Step 1: Understand the requirement

   To correctly get bottom view for hd [-1,1], must visit entire tree as in-range hd nodes may be reached via out-of-range parents.

2. Step 2: Standard traversal with filtered output

   Run standard level order, update map for all hd. When printing, iterate only over keys -1 to 1 in sorted order.

3. Final Answer:

   Store all nodes in map, then filter keys between -1 and 1 before printing -> Option A

4. Quick Check:

   Traverse all, map all hd, print filtered keys [OK]

Hint: Traverse all nodes, filter map keys when printing [OK]

Common Mistakes:

• Ignoring out-of-range nodes during traversal misses deeper in-range nodes
• Using stack breaks level order
• Preorder traversal disrupts bottom view order