Design Gurus Logo
Binary Tree Vertical Order Traversal (medium)

Problem Statement

Given the root of the binary tree, return the 2D list containing the vertical order traversal of the binary tree.

A vertical order traversal of the tree is defined as a top to bottom, column by column traversal.

Note: If two nodes are in the same row and column, keep its order from left to right.

Examples

Example 1:

  • Input: A binary tree: [1,2,3,4,5,6,7]
  • Expected Output: [[4], [2], [1,5,6], [3], [7]]
  • Justification: Nodes 4, 2, 1 with 5 and 6, 3, and 7 are in separate vertical lines. The nodes in each vertical line are listed in the order they appear from top to bottom.
Image

Example 2:

  • Input: A binary tree: [3,9,8,4,0,1,7]
  • Expected Output: [[4], [9], [3,0,1], [8], [7]]
  • Justification: Nodes are grouped based on their vertical positions. Lower nodes in the same vertical line follow the higher ones.
Image

Example 3:

  • Input: A binary tree: [3,null,20,15,7]
  • Expected Output: [[3, 15], [20], [7]]
  • Justification: The tree is skewed to the right. The output reflects the vertical traversal from left to right.
Image

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Unlock this and all other premium problems.
No code editor for this lesson
This lesson focuses on concepts and theory