Skip to main content

Binary Tree Column Order Traversal

Given a binary tree, return its column order traversal from top to bottom and left to right. Note: if two nodes are in the same row and column, order them from left to right.

Example(s)​

Example 1:

Tree:
    8
   / \
  2   29
     /  \
    3    9
Output: [[2],[8,3],[29],[9]]

Example 2:

Tree:
     100
    /   \
   53    78
  / \   /  \
 32  3  9   20
Output: [[32],[53],[100,3,9],[78],[20]]

Solution​

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * Perform column order traversal of a binary tree
 * @param {TreeNode} root - Root of the binary tree
 * @return {number[][]} - Column order traversal result
 */
function verticalOrder(root) {
  if (!root) return [];
  
  const map = new Map();
  const queue = [[root, 0, 0]]; // [node, col, row]
  let minCol = 0, maxCol = 0;
  
  while (queue.length) {
    const [node, col, row] = queue.shift();
    
    if (!map.has(col)) {
      map.set(col, []);
    }
    map.get(col).push([row, node.val]);
    
    minCol = Math.min(minCol, col);
    maxCol = Math.max(maxCol, col);
    
    if (node.left) queue.push([node.left, col - 1, row + 1]);
    if (node.right) queue.push([node.right, col + 1, row + 1]);
  }
  
  const result = [];
  for (let col = minCol; col <= maxCol; col++) {
    if (map.has(col)) {
      // Sort by row and then by value for same row
      const nodes = map.get(col)
        .sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0])
        .map(item => item[1]);
      result.push(nodes);
    }
  }
  
  return result;
}

Complexity​

  • Time Complexity: O(n log n) - Where n is the number of nodes, due to sorting nodes in each column
  • Space Complexity: O(n) - For storing nodes in the queue and hash map

Interactive Code Runner​

Test the Solution​

JavaScript Column Order Traversal Solution


function TreeNode(val, left, right) {
  this.val = (val===undefined ? 0 : val)
  this.left = (left===undefined ? null : left)
  this.right = (right===undefined ? null : right)
}

/**
* Perform column order traversal of a binary tree
* @param {TreeNode} root - Root of the binary tree
* @return {number[][]} - Column order traversal result
*/
function verticalOrder(root) {
if (!root) return [];

const map = new Map();
const queue = [[root, 0, 0]];
let minCol = 0, maxCol = 0;

while (queue.length) {
  const [node, col, row] = queue.shift();
  
  if (!map.has(col)) {
    map.set(col, []);
  }
  map.get(col).push([row, node.val]);
  
  minCol = Math.min(minCol, col);
  maxCol = Math.max(maxCol, col);
  
  if (node.left) queue.push([node.left, col - 1, row + 1]);
  if (node.right) queue.push([node.right, col + 1, row + 1]);
}

const result = [];
for (let col = minCol; col <= maxCol; col++) {
  if (map.has(col)) {
    const nodes = map.get(col)
      .sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0])
      .map(item => item[1]);
    result.push(nodes);
  }
}

return result;
}

// Test case 1: [8,2,29,3,9]
const tree1 = new TreeNode(8);
tree1.left = new TreeNode(2);
tree1.right = new TreeNode(29);
tree1.right.left = new TreeNode(3);
tree1.right.right = new TreeNode(9);

// Test case 2: [100,53,78,32,3,9,20]
const tree2 = new TreeNode(100);
tree2.left = new TreeNode(53);
tree2.right = new TreeNode(78);
tree2.left.left = new TreeNode(32);
tree2.left.right = new TreeNode(3);
tree2.right.left = new TreeNode(9);
tree2.right.right = new TreeNode(20);

// Test cases
console.log(verticalOrder(tree1)); // [[2],[8,3],[29],[9]]
console.log(verticalOrder(tree2)); // [[32],[53],[100,3,9],[78],[20]]
console.log(verticalOrder(null)); // []
Output:
Click "Run Code" to execute the code and see the results.

Takeaways​

  • Breadth-first search ensures nodes are processed level by level
  • Column tracking uses a hash map to group nodes by vertical position
  • Sorting by row and value ensures correct ordering within each column
  • Edge cases include empty tree, single-node tree, and nodes in the same row and column
  • O(n log n) time due to sorting nodes in each column