Preorder Traversal

Visit the root before each subtree, producing root-left-right order.

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.

preorder Preorder records the current node before visiting left and right subtrees.

Basic Implementation

                            basic.dart
                        
Replay: real traced execution (multi-file project)

                            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 preorder(Node? node, List<int> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }
void main() { final output = <int>[]; preorder(sampleTree(), output); print(listString(output)); }

                        
1tree ← 4(2(1,3),6(5,7)), output ← []1class Node {2  Node(this.value, [this.left, this.right]);⋯values this step4(2(1,3),6(5,7))tree[]output
2output ← [4]⋯13String listString(List<int> values) => "[${values.join(", ")}]";14void preorder(Node? node, List<int> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }15void main() { final output = <int>[]; preorder(sampleTree(), output); print(listString(output)); }values this step[] → [4]output4node
3output ← [4, 2]⋯13String listString(List<int> values) => "[${values.join(", ")}]";14void preorder(Node? node, List<int> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }15void main() { final output = <int>[]; preorder(sampleTree(), output); print(listString(output)); }values this step[4] → [4, 2]output2node
4output ← [4, 2, 1]⋯13String listString(List<int> values) => "[${values.join(", ")}]";14void preorder(Node? node, List<int> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }15void main() { final output = <int>[]; preorder(sampleTree(), output); print(listString(output)); }values this step[4, 2] → [4, 2, 1]output1node
5output ← [4, 2, 1, 3]⋯13String listString(List<int> values) => "[${values.join(", ")}]";14void preorder(Node? node, List<int> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }15void main() { final output = <int>[]; preorder(sampleTree(), output); print(listString(output)); }values this step[4, 2, 1] → [4, 2, 1, 3]output3node
6output ← [4, 2, 1, 3, 6]⋯13String listString(List<int> values) => "[${values.join(", ")}]";14void preorder(Node? node, List<int> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }15void main() { final output = <int>[]; preorder(sampleTree(), output); print(listString(output)); }values this step[4, 2, 1, 3] → [4, 2, 1, 3, 6]output6node
7output ← [4, 2, 1, 3, 6, 5]⋯13String listString(List<int> values) => "[${values.join(", ")}]";14void preorder(Node? node, List<int> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }15void main() { final output = <int>[]; preorder(sampleTree(), output); print(listString(output)); }values this step[4, 2, 1, 3, 6] → [4, 2, 1, 3, 6, 5]output5node
8output ← [4, 2, 1, 3, 6, 5, 7]⋯13String listString(List<int> values) => "[${values.join(", ")}]";14void preorder(Node? node, List<int> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }15void main() { final output = <int>[]; preorder(sampleTree(), output); print(listString(output)); }values this step[4, 2, 1, 3, 6, 5] → [4, 2, 1, 3, 6, 5, 7]output7node
9void main() { final output = <int>[]; preorder(sampleTree(), output); …⋯14void preorder(Node? node, List<int> output) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output); }15void main() { final output = <int>[]; preorder(sampleTree(), output); print(listString(output)); }values this step[4, 2, 1, 3, 6, 5, 7]output

Complexity

Time: O(n)
Space: O(h) recursion stack

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.