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 horizontal distance (HD) starting with root as 0. Left child has HD = parent HD - 1, right child has HD = parent HD + 1.

intermediate

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

A map or dictionary is used to store the latest node at each horizontal distance. A queue is used for level order traversal.

intermediate

In bottom view, if multiple nodes share the same horizontal distance, which node is visible?

The node that appears last in level order traversal (lowest level) at that horizontal distance is visible in the bottom view.

intermediate

What is the time complexity of computing 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 to compute the bottom view of a binary tree?

A Level order traversal

B Inorder traversal

C Postorder traversal

D Preorder traversal

Level order traversal visits nodes level by level, which helps track the bottom-most nodes at each horizontal distance.

If two nodes have the same horizontal distance, which one appears in the bottom view?

A The node at the lower level

B The node at the higher level

C The leftmost node

D The rightmost node

The node at the lower level (deeper in the tree) is visible in the bottom view.

What data structure is used to store the nodes visible in the bottom view?

A Stack

B Linked list

C Queue

D Map or dictionary

A map or dictionary stores the latest node at each horizontal distance.

What is the overall time complexity to find the bottom view of a binary tree with n nodes?

A O(n log n)

B O(log n)

C O(n)

D O(n^2)

Each node is visited once, so the time complexity is O(n).

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 the bottom view of a binary tree.

Consider how nodes at different depths affect visibility.