Top View of Binary Tree in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Top View of a binary tree?

The top view of a binary tree is the set of nodes visible when the tree is seen from above. It includes the nodes that are the first at each horizontal distance from the root.

beginner

How do we determine the horizontal distance (HD) of nodes in a binary tree?

The root node has HD = 0. For any node, its left child has HD = parent's HD - 1, and its right child has HD = parent's HD + 1.

intermediate

Which data structure is commonly used to find the top view of a binary tree?

A queue is used for level order traversal, and a map/dictionary stores the first node encountered at each horizontal distance.

intermediate

Why do we store only the first node at each horizontal distance when finding the top view?

Because the first node encountered at a horizontal distance during level order traversal is the topmost node visible from above at that horizontal distance.

intermediate

What is the time complexity of finding the top 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 is the horizontal distance of the root node in a binary tree?

A 0

B 1

C -1

D Depends on the tree height

The root node is assigned a horizontal distance of 0 by definition.

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

A Inorder traversal

B Preorder traversal

C Postorder traversal

D Level order traversal

Level order traversal visits nodes level by level, which helps identify the first node at each horizontal distance.

When two nodes share the same horizontal distance, which node is included in the top view?

A The one at the higher level

B The one at the lower level

C The rightmost node

D The leftmost node

The node at the higher (closer to root) level is visible from the top.

What data structure is used to keep track of nodes at each horizontal distance?

A Stack

B Queue

C Map or dictionary

D Linked list

A map/dictionary stores the first node encountered at each horizontal distance.

What is the output of the top view for a tree with nodes 1 (root), 2 (left child), and 3 (right child)?

A 1 -> 2 -> 3

B 2 -> 1 -> 3

C 1 only

D 2 -> 3

From top view, nodes 2, 1, and 3 are visible from left to right.

Explain how to find the top view of a binary tree step-by-step.

Think about how you see the tree from above and which nodes block others.

Why is level order traversal important for the top view of a binary tree?

Consider how nodes appear from top and which nodes hide others.