Top View of Binary Tree in DSA Typescript - 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

Why do we use a queue and a map/dictionary in the top view algorithm?

A queue helps in level order traversal (breadth-first), and a map stores the first node encountered at each horizontal distance to ensure only the topmost node is recorded.

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 the level order traversal.

intermediate

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

Only the first node encountered at that horizontal distance during level order traversal is included in the top view. Nodes at the same HD but lower levels are ignored.

What data structure is commonly used to perform the traversal for top view of a binary tree?

A Stack

B Queue

C Priority Queue

D Linked List

A queue is used for level order traversal which is essential to find the top view.

What is the horizontal distance of the root node in a binary tree?

A 0

B 1

C -1

D Depends on tree height

The root node is assigned a horizontal distance of 0.

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

A The leftmost node

B The node at the lower level

C The node at the higher level (closer to root)

D The rightmost node

The top view includes the node at the higher level for each horizontal distance.

Which data structure is used to store nodes by their horizontal distance in the top view algorithm?

A Stack

B Array

C Set

D Map or Dictionary

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

What is the overall time complexity of the top view algorithm for a binary tree with n nodes?

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

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

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

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

Describe the role of horizontal distance in the top view of a binary tree.

Imagine standing above the tree and looking down.