Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

130. Vertical Order Traversal of a Binary Tree

HardDay 38 of 60Trees & BST

Place the root of a binary tree at row 0, column 0. A node at (row, col) has its left child at (row + 1, col - 1) and its right child at (row + 1, col + 1). Return the vertical order traversal: one list per column from the leftmost column to the rightmost. Inside a column, list nodes from top to bottom, and when two nodes share the same row and column, put the smaller value first.

Example 1
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Column -1 has 9, column 0 has 3 then 15, column 1 has 20, column 2 has 7.
Example 2
Input: root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
5 and 6 are both at row 2, column 0, so the smaller value 5 comes first.
Constraints
  • 1 <= number of nodes <= 1000
  • 0 <= Node.val <= 1000
Hints
Frequently asked at: Meta, Amazon, Google, Flipkart
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min