Vertical Order Traversal of Binary Tree in DSA Javascript - 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

Why do we use a queue and a map/dictionary in Vertical Order Traversal?

Queue helps in level order traversal to visit nodes level by level. Map stores nodes grouped by their horizontal distance for final vertical order output.

beginner

What is the output format of Vertical Order Traversal?

Nodes are printed column-wise from leftmost to rightmost vertical line. Each column lists nodes top to bottom as they appear in the tree.

intermediate

How does Vertical Order Traversal differ from Level Order Traversal?

Level Order Traversal prints nodes level by level horizontally. Vertical Order Traversal groups nodes by vertical columns, which may mix levels.

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

A 0

B 1

C -1

D Depends on tree height

The root node is always assigned horizontal distance 0.

Which data structure is commonly used to keep track of nodes during Vertical Order Traversal?

A Queue

B Stack

C Set

D Linked List

Queue is used for level order traversal to visit nodes in order.

If a node has horizontal distance 2, what is the horizontal distance of its left child?

A 3

B 1

C 2

D 0

Left child has HD = parent's HD - 1, so 2 - 1 = 1.

What is the main purpose of the map/dictionary in Vertical Order Traversal?

A Store nodes by level

B Store nodes by value

C Store nodes grouped by horizontal distance

D Store nodes by insertion order

Map groups nodes by their horizontal distance for vertical columns.

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

A Postorder

B Inorder

C Preorder

D Level Order

Level order traversal is used to visit nodes level by level.

Explain how to perform Vertical Order Traversal on a binary tree step-by-step.

Think about horizontal distances and level order traversal.

Describe the difference between Vertical Order Traversal and Level Order Traversal.

Focus on grouping criteria and traversal direction.