Bottom View of Binary Tree in DSA Javascript - 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 in bottom view calculation?

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 processes nodes level by level, ensuring the bottom-most node at each horizontal distance overwrites previous nodes, giving the correct bottom view.

advanced

What is the output of bottom view for this tree?<br>Root: 20<br>Left child: 8<br>Right child: 22<br>Left child of 8: 5<br>Right child of 8: 3<br>Right child of 22: 25<br>Left child of 3: 10<br>Right child of 3: 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 0

B 1

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 of a binary tree?

A Postorder traversal

B Preorder traversal

C Inorder traversal

D Level order traversal

Level order traversal processes nodes level by level, which helps identify the bottom-most nodes.

In bottom view, what happens when two nodes share the same horizontal distance?

A The left-most node is chosen

B The bottom-most node is chosen

C The top-most node is chosen

D Both nodes are included

The bottom-most node at that horizontal distance is included in the bottom view.

Which data structure helps keep track of the latest node at each horizontal distance during bottom view calculation?

A Map or dictionary

B Stack

C Linked list

D Array

A map stores the latest node for each horizontal distance.

If a node is at horizontal distance 2 and level 3, and another node is at horizontal distance 2 and level 4, which node appears in the bottom view?

A Node at level 3

B Neither node

C Node at level 4

D Both nodes

The node at the lower level (level 4) is visible from the bottom.

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

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