zigzagTraversal<T> function

List<List<T>> zigzagTraversal<T>(BinaryTreeNode<T>? root)

Implementation

List<List<T>> zigzagTraversal<T>(BinaryTreeNode<T>? root) {
  final List<List<T>> result = [];

  if (root == null) return result;

  final List<BinaryTreeNode<T>> queue = [root];
  bool leftToRight = true;

  while (queue.isNotEmpty) {
    final int levelSize = queue.length;
    final List<T> currentLevel = [];

    for (int i = 0; i < levelSize; i++) {
      final BinaryTreeNode<T> node = queue.removeAt(0);

      if (leftToRight) {
        currentLevel.add(node.value);
      } else {
        currentLevel.insert(0, node.value);
      }

      if (node.left != null) {
        queue.add(node.left!);
      }
      if (node.right != null) {
        queue.add(node.right!);
      }
    }

    result.add(currentLevel);
    leftToRight = !leftToRight;
  }

  return result;
}