Vertical Order Traversal of a Binary Tree Hard 0 attempts
LeetCode ↗

Vertical Order Traversal of a Binary Tree

Hard TreeBinary TreeDFS LeetCode

Given a binary tree, return the vertical order traversal. Nodes at the same position are sorted by value.

Example: root = [3,9,20,null,null,15,7] → [[9],[3,15],[20],[7]]

Sample Input
—
Sample Output
—
Constraints
  • 1 <= number of nodes <= 1000
  • 0 <= Node.val <= 1000
Topics
TreeBinary TreeDFS

BFS with Column Tracking

function verticalTraversal(root) {
  const nodes = [];
  function dfs(node, row, col) {
    if (!node) return;
    nodes.push([col, row, node.val]);
    dfs(node.left, row+1, col-1);
    dfs(node.right, row+1, col+1);
  }
  dfs(root, 0, 0);
  nodes.sort((a,b) => a[0]-b[0] || a[1]-b[1] || a[2]-b[2]);
  const result = []; let prevCol = -Infinity;
  for (const [col,,val] of nodes) {
    if (col !== prevCol) { result.push([]); prevCol = col; }
    result[result.length-1].push(val);
  }
  return result;
}

Time: O(n log n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript