Vertical Order Traversal of a Binary Tree

Given the root of a binary tree, calculate the vertical order traversal. Each node at position (row, col) has its left and right children at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The traversal should be a list of top-to-bottom orderings for each column index, starting from the leftmost column to the rightmost. If there are multiple nodes in the same row and column, sort them by their values.

Constraints

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 1000
View editorial solution
Saving… · 9 lines
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right

class Solution:
def verticalOrderTraversal(self, root: TreeNode) -> List[List[int]]:
Console

Click Run to execute sample tests.