Trees

Level-Order Traversal

Visit a tree breadth-first with a queue.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Dart DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.dart 
class Node {
  Node(this.value, [this.left, this.right]);
  final int value;
  Node? left;
  Node? right;
}
String render(Node? node) {
  if (node == null) return "_";
  if (node.left == null && node.right == null) return node.value.toString();
  return "${node.value}(${render(node.left)},${render(node.right)})";
}
Node sampleTree() => Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)));
String listString(List<int> values) => "[${values.join(", ")}]";
void main() { final queue = <Node>[sampleTree()]; final output = <int>[]; while (queue.isNotEmpty) { final node = queue.removeAt(0); output.add(node.value); if (node.left != null) queue.add(node.left!); if (node.right != null) queue.add(node.right!); } print(listString(output)); }

Complexity

  • Time: O(n)
  • Space: O(w) queue space

Implementation notes

  • Render tree structure explicitly instead of printing node objects.
  • The replay highlights the node, traversal state, queue, path, or search cursor that changes at each step.
level order Level-order traversal uses a queue to visit shallower nodes first.