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

Recall & Review

beginner

What does the Top View of a binary tree represent?

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

beginner

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

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 algorithm to find the top view of a binary tree?

The queue helps in level order traversal (breadth-first), ensuring nodes are processed top-down. The map stores the first node encountered at each horizontal distance, which forms the top view.

intermediate

What is the time complexity of finding the top view of a binary tree using level order traversal?

The time complexity is O(n), where n is the number of nodes, because each node is visited once during the 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 hidden behind.

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

A 1

B 0

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 Level order traversal

B Preorder traversal

C Postorder traversal

D Inorder traversal

Level order traversal processes nodes level by level, which helps identify the topmost nodes at each horizontal distance.

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

A The node at the lower level

B The right child node

C Both nodes appear

D The node at the higher level

The node at the higher (closer to root) level is visible from the top, so it appears in the top view.

What data structure is used to store the first node at each horizontal distance?

A Stack

B Queue

C Map or Dictionary

D Linked List

A map or dictionary stores nodes keyed by their horizontal distance to track the first node encountered.

What is the output of the top view for a single-node binary tree?

A The single node itself

B Empty

C Null

D Depends on the node value

With only one node, the top view is just that node.

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

Think about how to visit nodes and remember which ones are visible from the top.

Describe why level order traversal is preferred over inorder or preorder for the top view problem.

Consider the order in which nodes appear from top to bottom.