Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Vertical Order Traversal of a Binary Tree

Explore how to implement vertical order traversal of a binary tree by grouping nodes based on their horizontal position using breadth-first search. Learn to return nodes from leftmost to rightmost columns and handle cases where nodes share the same row and column.

We'll cover the following...

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 the following coding playground.

Java
usercode > Solution.java
// Definiton of a binary tree node class

// class TreeNode<T> {

//     T data;

//     TreeNode<T> left;

//     TreeNode<T> right;



//     TreeNode(T data) {

//         this.data = data;

//         this.left = null;

//         this.right = null;

//     }

// }



import java.util.*;

import ds_v1.BinaryTree.TreeNode;



public class Solution{



  public static List<List<Integer>> verticalOrder(TreeNode<Integer> root) {



        // Replace this placeholder return statament with your code

        return new ArrayList<List<Integer>>();

  }

}
Vertical Order Traversal of a Binary Tree