Data Structure in Dart – Trees

Let’s continue with Trees, one of the most important and conceptually rich topics in Data Structures. This module is foundational for databases, file systems, UI hierarchies and compilers.

---

1. What Is a Tree?

A Tree is a non-linear hierarchical data structure used to represent relationships between elements.

Unlike arrays or linked lists:

• Data is organized in levels
• Each element can have children
• There is a single root

Real-world examples

• File system (folders & files)
• UI widget tree in Flutter
• Organization charts
• HTML / DOM structure

---

2. Basic Terminology

        A
       / \
      B   C
     / \
    D   E

• Root → A
• Parent → A is parent of B, C
• Child → B, C
• Leaf → D, E, C
• Height → longest path from root to leaf
• Depth → distance from root

---

3. Types of Trees

• General Tree
• Binary Tree
• Binary Search Tree (BST)
• Balanced Trees (AVL, Red-Black)
• Heap
• Trie (Prefix Tree)

In this module, we focus on Binary Trees first.

---

4. Binary Tree

A Binary Tree is a tree where:

• Each node has at most two children
• Left child
• Right child

Node Structure in Dart

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

  TreeNode(this.value);
}

---

5. Tree Traversals

Traversal means visiting all nodes in a specific order.

---

1. Inorder Traversal (Left → Root → Right)

Left → Root → Right

void inorder(TreeNode<int>? node) {
  if (node == null) return;
  inorder(node.left);
  print(node.value);
  inorder(node.right);
}

Use case:

• Produces sorted order in BST

---

2. Preorder Traversal (Root → Left → Right)

Root → Left → Right

void preorder(TreeNode<int>? node) {
  if (node == null) return;
  print(node.value);
  preorder(node.left);
  preorder(node.right);
}

Use case:

• Tree cloning
• Serialization

---

3. Postorder Traversal (Left → Right → Root)

Left → Right → Root

void postorder(TreeNode<int>? node) {
  if (node == null) return;
  postorder(node.left);
  postorder(node.right);
  print(node.value);
}

Use case:

• Deleting trees
• Expression trees

---

4. Level Order Traversal (BFS)

Uses a Queue

import 'dart:collection';

void levelOrder(TreeNode<int>? root) {
  if (root == null) return;

  Queue<TreeNode<int>> queue = Queue();
  queue.add(root);

  while (queue.isNotEmpty) {
    var node = queue.removeFirst();
    print(node.value);

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

---

6. Binary Search Tree (BST)

A BST follows strict rules:

• Left subtree → values less than root
• Right subtree → values greater than root

        10
       /  \
      5    20
     / \     \
    3   7     30

---

Insert into BST

TreeNode<int>? insertBST(TreeNode<int>? root, int value) {
  if (root == null) return TreeNode(value);

  if (value < root.value) {
    root.left = insertBST(root.left, value);
  } else {
    root.right = insertBST(root.right, value);
  }
  return root;
}

---

Search in BST

bool searchBST(TreeNode<int>? root, int value) {
  if (root == null) return false;
  if (root.value == value) return true;
  return value < root.value
      ? searchBST(root.left, value)
      : searchBST(root.right, value);
}

---

7. Time Complexity (BST)

Operation	Average	Worst
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

Worst case happens when tree becomes skewed.

---

8. Balanced Trees (Concept)

To avoid skewed trees:

• AVL Trees
• Red-Black Trees

They automatically rebalance to maintain height ≈ log n.

Used in:

• Databases
• Language libraries
• Ordered Maps/Sets

(Usually implemented internally — rarely handwritten in Flutter apps.)

---

9. Heap (Special Tree)

A Heap is a complete binary tree:

• Min Heap → parent ≤ children
• Max Heap → parent ≥ children

Common Uses

• Priority Queue
• Scheduling
• Dijkstra algorithm

---

Min Heap Example (Conceptual)

import 'dart:collection';

void main() {
  PriorityQueue<int> minHeap =
      PriorityQueue((a, b) => a.compareTo(b));

  minHeap.add(10);
  minHeap.add(5);
  minHeap.add(20);

  print(minHeap.removeFirst()); // 5
}

---

10. Flutter Real-World Example – Widget Tree

Flutter UI is a tree:

MaterialApp
 └─ Scaffold
    └─ Column
       ├─ Text
       ├─ Button
       └─ ListView

Understanding trees helps you:

• Optimize rebuilds
• Understand widget lifecycle
• Debug layout issues

---

11. Classic Tree Problems

• Height of a tree
• Diameter of a tree
• Lowest Common Ancestor (LCA)
• Check if tree is balanced
• Validate a BST

Example: Height

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

---

12. Tree vs Other Structures

Structure	Best For
Array	Fast indexing
Linked List	Fast insert/delete
Tree	Hierarchical data
Hash Table	Fast lookup
Graph	Complex relationships

---

13. Summary

• Trees store hierarchical data
• Traversals are core to tree algorithms
• BST enables fast search
• Heaps support priority-based tasks
• Trees power Flutter UI, databases, file systems

---

Coming Next: Graphs

we’ll cover:

• Graph representations
• DFS & BFS
• Shortest paths
• Real-world graph problems