Implement a binary tree in Dart and write functions for: (a) In-order traversal, (b) Pre-order traversal, (c) Post-order traversal, (d) Level-order traversal (BFS).

Overview

Binary Tree is a hierarchical data structure where each node has at most two children: left and right. Unlike linear structures (arrays, linked lists), trees represent hierarchical relationships and are essential for searching, sorting, and organizing hierarchical data.

Binary trees are fundamental to computer science, used in compilers (expression trees), databases (B-trees for indexing), file systems (directory structures), and many algorithms. Understanding tree traversals is crucial for technical interviews and real-world problem solving.

Key characteristics:

• Each node has at most 2 children (left, right)
• Has a root node (topmost)
• Nodes without children are leaves
• Height: longest path from root to leaf
• Different traversal orders produce different sequences

When to use:

• Hierarchical data (file systems, org charts)
• Binary Search Trees (O(log n) search)
• Expression parsing (operator precedence)
• Huffman coding (compression)
• Decision trees (machine learning)

---

Core Concepts

Binary Tree Structure:

textCopy
        1           ← Root
       / \
      2   3         ← Internal nodes
     / \   \
    4   5   6       ← Leaves

Tree Terminology:

• Root: Top node (1)
• Parent: Node with children (2 is parent of 4, 5)
• Child: Node below parent (4, 5 are children of 2)
• Leaf: Node with no children (4, 5, 6)
• Height: Longest path from root to leaf (2 in example)
• Depth: Distance from root to node
• Level: All nodes at same depth

---

Tree Node Class

dartCopy
class TreeNode<T> {
  T value;
  TreeNode<T>? left;
  TreeNode<T>? right;

  TreeNode(this.value, [this.left, this.right]);

  @override
  String toString() => value.toString();
}

---

Binary Tree Class

dartCopy
class BinaryTree<T> {
  TreeNode<T>? root;

  BinaryTree([this.root]);

  /// Helper to build tree from list (level-order)
  static BinaryTree<int> fromList(List<int?> values) {
    if (values.isEmpty || values[0] == null) {
      return BinaryTree<int>();
    }

    final root = TreeNode<int>(values[0]!);
    final queue = <TreeNode<int>>[root];
    int i = 1;

    while (i < values.length && queue.isNotEmpty) {
      final node = queue.removeAt(0);

      // Left child
      if (i < values.length && values[i] != null) {
        node.left = TreeNode<int>(values[i]!);
        queue.add(node.left!);
      }
      i++;

      // Right child
      if (i < values.length && values[i] != null) {
        node.right = TreeNode<int>(values[i]!);
        queue.add(node.right!);
      }
      i++;
    }

    return BinaryTree<int>(root);
  }

  /// Get height of tree - O(n)
  int height([TreeNode<T>? node]) {
    node ??= root;
    if (node == null) return -1;

    int leftHeight = height(node.left);
    int rightHeight = height(node.right);

    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
  }

  /// Count total nodes - O(n)
  int size([TreeNode<T>? node]) {
    node ??= root;
    if (node == null) return 0;

    return 1 + size(node.left) + size(node.right);
  }

  /// Check if tree is empty
  bool get isEmpty => root == null;
  bool get isNotEmpty => root != null;
}

---

Traversal 1: In-Order (Left, Root, Right)

Order: Visit left subtree → root → right subtree

Use case: Gets elements in sorted order for Binary Search Tree

Visualization:

textCopy
        1
       / \
      2   3
     / \
    4   5

In-order: 4, 2, 5, 1, 3

Recursive Implementation:

dartCopy
extension InOrderTraversal<T> on BinaryTree<T> {
  /// In-order traversal (recursive) - O(n)
  List<T> inOrderRecursive([TreeNode<T>? node]) {
    node ??= root;
    if (node == null) return [];

    final result = <T>[];

    result.addAll(inOrderRecursive(node.left));    // Left
    result.add(node.value);                         // Root
    result.addAll(inOrderRecursive(node.right));   // Right

    return result;
  }
}

Iterative Implementation (Using Stack):

dartCopy
extension InOrderTraversalIterative<T> on BinaryTree<T> {
  /// In-order traversal (iterative) - O(n) time, O(h) space
  List<T> inOrderIterative() {
    if (root == null) return [];

    final result = <T>[];
    final stack = <TreeNode<T>>[];
    TreeNode<T>? current = root;

    while (current != null || stack.isNotEmpty) {
      // Go to leftmost node
      while (current != null) {
        stack.add(current);
        current = current.left;
      }

      // Current is null, pop from stack
      current = stack.removeLast();
      result.add(current.value);

      // Visit right subtree
      current = current.right;
    }

    return result;
  }
}

---

Traversal 2: Pre-Order (Root, Left, Right)

Order: Visit root → left subtree → right subtree

Use case: Copy tree, create prefix expression

Visualization:

textCopy
        1
       / \
      2   3
     / \
    4   5

Pre-order: 1, 2, 4, 5, 3

Recursive Implementation:

dartCopy
extension PreOrderTraversal<T> on BinaryTree<T> {
  /// Pre-order traversal (recursive) - O(n)
  List<T> preOrderRecursive([TreeNode<T>? node]) {
    node ??= root;
    if (node == null) return [];

    final result = <T>[];

    result.add(node.value);                         // Root
    result.addAll(preOrderRecursive(node.left));   // Left
    result.addAll(preOrderRecursive(node.right));  // Right

    return result;
  }
}

Iterative Implementation:

dartCopy
extension PreOrderTraversalIterative<T> on BinaryTree<T> {
  /// Pre-order traversal (iterative) - O(n) time, O(h) space
  List<T> preOrderIterative() {
    if (root == null) return [];

    final result = <T>[];
    final stack = <TreeNode<T>>[root!];

    while (stack.isNotEmpty) {
      final node = stack.removeLast();
      result.add(node.value);

      // Push right first (so left is processed first)
      if (node.right != null) stack.add(node.right!);
      if (node.left != null) stack.add(node.left!);
    }

    return result;
  }
}

---

Traversal 3: Post-Order (Left, Right, Root)

Order: Visit left subtree → right subtree → root

Use case: Delete tree, postfix expression

Visualization:

textCopy
        1
       / \
      2   3
     / \
    4   5

Post-order: 4, 5, 2, 3, 1

Recursive Implementation:

dartCopy
extension PostOrderTraversal<T> on BinaryTree<T> {
  /// Post-order traversal (recursive) - O(n)
  List<T> postOrderRecursive([TreeNode<T>? node]) {
    node ??= root;
    if (node == null) return [];

    final result = <T>[];

    result.addAll(postOrderRecursive(node.left));   // Left
    result.addAll(postOrderRecursive(node.right));  // Right
    result.add(node.value);                          // Root

    return result;
  }
}

Iterative Implementation (Two Stacks):

dartCopy
extension PostOrderTraversalIterative<T> on BinaryTree<T> {
  /// Post-order traversal (iterative) - O(n) time, O(h) space
  List<T> postOrderIterative() {
    if (root == null) return [];

    final result = <T>[];
    final stack1 = <TreeNode<T>>[root!];
    final stack2 = <TreeNode<T>>[];

    // Push nodes to stack2 in reverse post-order
    while (stack1.isNotEmpty) {
      final node = stack1.removeLast();
      stack2.add(node);

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

    // Pop from stack2 to get post-order
    while (stack2.isNotEmpty) {
      result.add(stack2.removeLast().value);
    }

    return result;
  }
}

---

Traversal 4: Level-Order (BFS - Breadth-First Search)

Order: Visit nodes level by level (top to bottom, left to right)

Use case: Find shortest path, level-wise processing

Visualization:

textCopy
        1           ← Level 0
       / \
      2   3         ← Level 1
     / \   \
    4   5   6       ← Level 2

Level-order: 1, 2, 3, 4, 5, 6

Implementation (Using Queue):

dartCopy
extension LevelOrderTraversal<T> on BinaryTree<T> {
  /// Level-order traversal (BFS) - O(n) time, O(w) space
  /// where w is maximum width of tree
  List<T> levelOrder() {
    if (root == null) return [];

    final result = <T>[];
    final queue = <TreeNode<T>>[root!];

    while (queue.isNotEmpty) {
      final node = queue.removeAt(0);  // Dequeue
      result.add(node.value);

      // Enqueue children (left to right)
      if (node.left != null) queue.add(node.left!);
      if (node.right != null) queue.add(node.right!);
    }

    return result;
  }

  /// Level-order traversal with level separation
  List<List<T>> levelOrderByLevels() {
    if (root == null) return [];

    final result = <List<T>>[];
    final queue = <TreeNode<T>>[root!];

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

      for (int i = 0; i < levelSize; i++) {
        final node = queue.removeAt(0);
        currentLevel.add(node.value);

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

      result.add(currentLevel);
    }

    return result;
  }
}

---

Complete Example with All Traversals

dartCopy
void main() {
  // Build tree:
  //        1
  //       / \
  //      2   3
  //     / \   \
  //    4   5   6

  final tree = BinaryTree.fromList([1, 2, 3, 4, 5, null, 6]);

  print('In-order (Recursive):   ${tree.inOrderRecursive()}');
  // Output: [4, 2, 5, 1, 3, 6]

  print('In-order (Iterative):   ${tree.inOrderIterative()}');
  // Output: [4, 2, 5, 1, 3, 6]

  print('Pre-order (Recursive):  ${tree.preOrderRecursive()}');
  // Output: [1, 2, 4, 5, 3, 6]

  print('Pre-order (Iterative):  ${tree.preOrderIterative()}');
  // Output: [1, 2, 4, 5, 3, 6]

  print('Post-order (Recursive): ${tree.postOrderRecursive()}');
  // Output: [4, 5, 2, 6, 3, 1]

  print('Post-order (Iterative): ${tree.postOrderIterative()}');
  // Output: [4, 5, 2, 6, 3, 1]

  print('Level-order (BFS):      ${tree.levelOrder()}');
  // Output: [1, 2, 3, 4, 5, 6]

  print('Level-order by levels:  ${tree.levelOrderByLevels()}');
  // Output: [[1], [2, 3], [4, 5, 6]]

  print('Height: ${tree.height()}');  // 2
  print('Size: ${tree.size()}');      // 6
}

---

Traversal Comparison Table

Complexity for all:

• Time: O(n) - visit each node once
• Space: O(h) for recursive (call stack), O(w) for level-order queue

Where:

• n = number of nodes
• h = height of tree
• w = maximum width of tree

---

Use Case Example: Expression Tree

Parse and evaluate mathematical expressions.

dartCopy
class ExpressionTree extends BinaryTree<String> {
  ExpressionTree(TreeNode<String> root) : super(root);

  /// Build expression tree from postfix notation
  static ExpressionTree fromPostfix(String postfix) {
    final tokens = postfix.split(' ');
    final stack = <TreeNode<String>>[];
    final operators = {'+', '-', '*', '/'};

    for (var token in tokens) {
      if (operators.contains(token)) {
        final right = stack.removeLast();
        final left = stack.removeLast();
        final node = TreeNode(token, left, right);
        stack.add(node);
      } else {
        stack.add(TreeNode(token));
      }
    }

    return ExpressionTree(stack.last);
  }

  /// Evaluate expression tree
  double evaluate([TreeNode<String>? node]) {
    node ??= root;
    if (node == null) return 0;

    // Leaf node: operand
    if (node.left == null && node.right == null) {
      return double.parse(node.value);
    }

    // Internal node: operator
    double left = evaluate(node.left);
    double right = evaluate(node.right);

    switch (node.value) {
      case '+': return left + right;
      case '-': return left - right;
      case '*': return left * right;
      case '/': return left / right;
      default: throw ArgumentError('Unknown operator: ${node.value}');
    }
  }

  /// Get infix notation (with parentheses)
  String toInfix([TreeNode<String>? node]) {
    node ??= root;
    if (node == null) return '';

    // Leaf: just the value
    if (node.left == null && node.right == null) {
      return node.value;
    }

    // Internal: (left op right)
    return '(${toInfix(node.left)} ${node.value} ${toInfix(node.right)})';
  }

  /// Get prefix notation
  String toPrefix([TreeNode<String>? node]) {
    node ??= root;
    if (node == null) return '';

    if (node.left == null && node.right == null) {
      return node.value;
    }

    return '${node.value} ${toPrefix(node.left)} ${toPrefix(node.right)}';
  }
}

void main() {
  // Expression: (3 + 4) * 2
  // Postfix: 3 4 + 2 *

  final tree = ExpressionTree.fromPostfix('3 4 + 2 *');

  print('Infix:  ${tree.toInfix()}');      // ((3 + 4) * 2)
  print('Prefix: ${tree.toPrefix()}');     // * + 3 4 2
  print('Result: ${tree.evaluate()}');     // 14.0

  // Tree structure:
  //       *
  //      / \
  //     +   2
  //    / \
  //   3   4
}

---

Best Practices

1. Choose Right Traversal

dartCopy
// ✅ In-order for sorted output (BST)
List<int> sorted = bst.inOrderRecursive();

// ✅ Pre-order to copy tree structure
TreeNode copyTree(TreeNode node) {
  // Pre-order: create root first
  return TreeNode(
    node.value,
    node.left != null ? copyTree(node.left!) : null,
    node.right != null ? copyTree(node.right!) : null,
  );
}

// ✅ Post-order to delete tree
void deleteTree(TreeNode? node) {
  if (node == null) return;
  deleteTree(node.left);   // Delete left
  deleteTree(node.right);  // Delete right
  // Delete root last
}

// ✅ Level-order for BFS
List<int> bfs = tree.levelOrder();

2. Handle Null Nodes

dartCopy
// ✅ Good - check for null
if (node != null) {
  print(node.value);
}

// ❌ Bad - may crash
print(node!.value);  // Throws if null!

3. Use Iteration for Production

dartCopy
// ✅ Good - iterative (no stack overflow)
List<T> inOrder = tree.inOrderIterative();

// ⚠️ Caution - recursive (may overflow on deep trees)
List<T> inOrder = tree.inOrderRecursive();

---

Interview Tips

Common Interview Questions:

Q: "Explain all tree traversals"

• In-order: Left → Root → Right (sorted for BST)
• Pre-order: Root → Left → Right (copy tree)
• Post-order: Left → Right → Root (delete tree)
• Level-order: Level by level (BFS, shortest path)

Q: "When to use each traversal?"

• In-order: Get sorted elements from BST
• Pre-order: Serialize/copy tree structure
• Post-order: Delete tree, evaluate expression tree
• Level-order: Find shortest path, level-wise operations

Q: "Recursive vs Iterative?"

• Recursive: Simpler code, uses call stack (may overflow)
• Iterative: More complex, explicit stack/queue (no overflow)
• Use iterative for production (deep trees)

Q: "Find height of tree"

dartCopy
int height(TreeNode? node) {
  if (node == null) return -1;
  return 1 + max(height(node.left), height(node.right));
}

Follow-up Questions:

• "Binary tree vs BST?" → No order vs left < root < right
• "DFS vs BFS?" → Stack (recursion) vs Queue
• "Time/space complexity?" → O(n) time, O(h) space for DFS

Red Flags to Avoid:

• Confusing traversal orders ❌
• Not knowing use cases for each ❌
• Forgetting base case in recursion ❌
• Not handling null nodes ❌

---

Resources

• Binary Tree - Wikipedia
• Tree Traversal - Wikipedia
• Binary Tree Visualization