verticalOrderTraversal<T> function

List<List<T>> verticalOrderTraversal<T>(
  1. BinaryTreeNode<T>? root
)

Implementation

List<List<T>> verticalOrderTraversal<T>(BinaryTreeNode<T>? root) {
  if (root == null) return [];
  final Map<int, List<T>> columnTable = {};
  final Queue<MapEntry<BinaryTreeNode<T>, int>> queue = Queue();
  queue.add(MapEntry(root, 0));
  int minCol = 0, maxCol = 0;
  while (queue.isNotEmpty) {
    final entry = queue.removeFirst();
    final node = entry.key;
    final col = entry.value;
    columnTable.putIfAbsent(col, () => []).add(node.value);
    if (node.left != null) {
      queue.add(MapEntry(node.left!, col - 1));
      minCol = minCol < col - 1 ? minCol : col - 1;
    }
    if (node.right != null) {
      queue.add(MapEntry(node.right!, col + 1));
      maxCol = maxCol > col + 1 ? maxCol : col + 1;
    }
  }
  return [for (int i = minCol; i <= maxCol; ++i) columnTable[i] ?? []];
}