Trees

Build a Binary Tree

Create a fixed seven-node binary tree and render its shape.

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.

node links A node stores one value plus references to its left and right children.

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 main() { print(render(sampleTree())); }

  1. node ← 1, tree ← 1

    11}12Node sampleTree() => Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)));13String listString(List<int> values) => "[${values.join(", ")}]";
    values this step1node1tree

  2. node ← 3, tree ← 1, 3

    11}12Node sampleTree() => Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)));13String listString(List<int> values) => "[${values.join(", ")}]";
    values this step3node1, 3tree

  3. node ← 2, tree ← 2(1,3)

    11}12Node sampleTree() => Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)));13String listString(List<int> values) => "[${values.join(", ")}]";
    values this step2node2(1,3)tree

  4. node ← 5, tree ← 2(1,3), 5

    11}12Node sampleTree() => Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)));13String listString(List<int> values) => "[${values.join(", ")}]";
    values this step5node2(1,3), 5tree

  5. node ← 7, tree ← 2(1,3), 5, 7

    11}12Node sampleTree() => Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)));13String listString(List<int> values) => "[${values.join(", ")}]";
    values this step7node2(1,3), 5, 7tree

  6. node ← 6, tree ← 2(1,3), 6(5,7)

    11}12Node sampleTree() => Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)));13String listString(List<int> values) => "[${values.join(", ")}]";
    values this step6node2(1,3), 6(5,7)tree

  7. node ← 4, tree ← 4(2(1,3),6(5,7))

    11}12Node sampleTree() => Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)));13String listString(List<int> values) => "[${values.join(", ")}]";
    values this step4node4(2(1,3),6(5,7))tree

  8. stdout ← 4(2(1,3),6(5,7))

    13String listString(List<int> values) => "[${values.join(", ")}]";14void main() { print(render(sampleTree())); }
    values this step4(2(1,3),6(5,7))stdout4(2(1,3),6(5,7))tree

Complexity

  • Time: O(n)
  • Space: O(n)

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.