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

Vertical Order Traversal of a Binary Tree

Hard TreeBinary TreeDFS LeetCode

You're given a binary tree. Return its vertical order traversal: group nodes into columns based on how many steps left or right they sit from the root (a left child shifts one column left, a right child one column right), list the columns from leftmost to rightmost, and within a column read nodes top to bottom. Nodes tied on the same position are ordered by ascending value.

Input Format
Implement verticalTraversal(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
root = [3,9,20,null,null,15,7]
Output
[[9],[3,15],[20],[7]]

Example 2

Input
root = [1]
Output
[[1]]
Constraints
  • 1 <= number of nodes <= 1000
  • 0 <= Node.val <= 1000
Test Cases (2)
Case 1
Args: [[3,9,20,null,null,15,7]] Expected: [[9],[3,15],[20],[7]]
Case 2
Args: [[1]] Expected: [[1]]
Topics
TreeBinary TreeDFS

DFS with Coordinate Sorting

javascript
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