Vertical Order Traversal of Binary Tree in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is Vertical Order Traversal of a Binary Tree?

It is a way to print the nodes of a binary tree column by column, from left to right. Nodes in the same vertical line are grouped together.

beginner

How do we assign horizontal distances (HD) to nodes in Vertical Order Traversal?

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

intermediate

Which data structure is commonly used to store nodes by their horizontal distance during Vertical Order Traversal?

A map (or dictionary) where keys are horizontal distances and values are lists of nodes at that distance.

intermediate

Why do we use a queue in the Vertical Order Traversal algorithm?

A queue helps perform level order traversal (breadth-first search) to visit nodes level by level, ensuring correct vertical grouping.

advanced

What is the output order of nodes in Vertical Order Traversal when multiple nodes share the same horizontal distance and level?

Nodes are output in the order they appear in the level order traversal, i.e., from top to bottom and left to right within the same vertical line.

In Vertical Order Traversal, what horizontal distance is assigned to the root node?

A 1

B 0

C -1

D Depends on tree height

The root node is always assigned horizontal distance 0.

Which traversal method is used to visit nodes in Vertical Order Traversal?

A Preorder

B Inorder

C Level order (BFS)

D Postorder

Level order traversal (using a queue) is used to visit nodes level by level.

What data structure is best to store nodes grouped by their horizontal distance?

A Linked list

B Stack

C Array

D Map or dictionary

A map/dictionary stores nodes by horizontal distance keys efficiently.

If a node is at horizontal distance 2, where is it located relative to the root?

A Two steps right

B Two steps left

C At root

D Cannot determine

Positive horizontal distance means right side of the root.

How are nodes ordered when multiple nodes share the same horizontal distance and level?

A Order of appearance in level order traversal

B Random order

C Sorted by depth

D Sorted by value

Nodes are output in the order they appear in level order traversal.

Explain the steps to perform Vertical Order Traversal of a binary tree.

Think about how to visit nodes and group them by vertical lines.

Describe how horizontal distances change when moving to left and right children in a binary tree.

Consider the root as center and left/right as steps left or right.