Search⌘ K
AI Features

Vertical Order Traversal of a Binary Tree

Vertical Order Traversal of a Binary Tree returns node values grouped by column from left to right, with each column ordered top to bottom and left to right for ties.

Statement

Given the root of a binary tree, return the vertical order traversal of its nodes' values.

The nodes should be grouped into columns based on their horizontal position in the tree:

  • The root is at column 0.

  • The left child of a node is one column to the left of its parent.

  • The right child of a node is one column to the right of its parent.

  • Return the columns from the leftmost column to the rightmost column.

  • Within each column, return nodes from top to bottom.

  • If two nodes have the same row and column, they should appear from left to right.

Constraints:

  • The number of nodes in the tree is in the range [0, 100].

  • −100≤-100 ≤ Node.val ≤100≤ 100

Examples

canvasAnimation-image
1 / 3

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Vertical Order Traversal of a Binary Tree

1.

What should be the output if the following tree is given as input?

tree = [25, 14, 35, -1, 15, null, 200, null, 10, null, null, 90, 350]

          __ 25 _ 
         |       |
      __ 14 _    35 _ 
     |       |       |
     -1 _    15   __ 200 _ 
         |       |        |
         10      90       350 
A.

[[25], [14, 35], [-1, 15, 200], [10, 90, 350]]

B.

[[-1], [14, 10], [25, 15], [35, 90], [200], [350]]

C.

[[-1], [14], [10], [25], [15], [35], [90], [200], [350]]

D.

[[25, 14, -1], [10], [14, 15], [200, 90], [125, 35, 200, 350]]


1 / 2

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.

1
2
3
4
5

Try it yourself

Implement your solution in main.go in the following coding playground. We have provided a useful code template in the other file that you may build on to solve this problem.

Go
usercode > main.go
package main
import (. "golang-test-code/ds_v1/BinaryTree") // TreeNode[T]
func verticalOrder(root *TreeNode[int]) [][]int {
// Replace this placeholder return statament with your code
return make([][]int, 0)
}
Vertical Order Traversal of a Binary Tree