Trees

Trees: Hierarchical Data Organization

A tree is a hierarchical data structure consisting of nodes connected by edges, with a single root node and no cycles. Trees model hierarchical relationships and enable efficient searching, sorting, and organizing of data through their recursive, branching structure.

Key characteristics:

• Single root node - Entry point for all operations
• Parent-child relationships - Clear hierarchical structure
• No cycles - Acyclic structure ensures predictable traversal
• Recursive subtrees - Each node can be the root of its own subtree

Tree Structure Overview

Basic Tree Components:

graph TD
    A["Root Node"] --> B["Child 1"]
    A --> C["Child 2"]
    B --> D["Leaf Node"]
    B --> E["Leaf Node"]
    C --> F["Leaf Node"]

    style A fill:#e3f2fd
    style D fill:#c8e6c9
    style E fill:#c8e6c9
    style F fill:#c8e6c9

Tree Properties:

graph LR
    A["Tree Properties"] --> B["Acyclic<br/>No circular references"]
    A --> C["Connected<br/>All nodes reachable"]
    A --> D["Hierarchical<br/>Parent-child relationships"]
    A --> E["Recursive<br/>Subtrees are trees"]

    style A fill:#fff3e0
    style B fill:#e8f5e8
    style C fill:#e8f5e8
    style D fill:#e8f5e8
    style E fill:#e8f5e8

Tree Terminology

Essential Terms:

• Root: Topmost node with no parent
• Parent/Child: Direct relationships between connected nodes
• Leaf: Node with no children (terminal nodes)
• Siblings: Nodes sharing the same parent
• Ancestors/Descendants: Indirect relationships through the tree path
• Height: Longest path from root to any leaf
• Depth: Distance from root to a specific node
• Level: All nodes at the same depth from root

Why Tree Operation Complexity Matters

The efficiency of fundamental operations—search, insert, and delete—on tree structures depends on the specific type and balance of the tree. These complexities are important because they impact the performance of real-world tasks like database indexing, file systems, and searching large datasets.

• Unbalanced Binary Search Trees (BSTs): In the worst case (e.g., inserting sorted data), an unbalanced BST can become a linked list, making search and updates slow at O(n). On average, if the data is random, the height is closer to log n, so average operations are faster.
• Balanced BSTs (e.g., AVL, Red-Black Trees): These ensure the height stays near log n by automatically rebalancing themselves after inserts and deletes, so all major operations remain fast.
• B-Trees: Commonly used in databases and filesystems, B-Trees are kept balanced by allowing each node to have more than two children (not just left and right). This multi-child structure ensures that the tree stays shallow, so search, insert, and delete operations are consistently efficient at O(log n).

Below is a comparison of time complexities for common tree operations:

Operation	Unbalanced BST	Balanced BST / AVL / Red-Black	B-Tree
Search	O(n) worst, O(log n) avg	O(log n)	O(log n)
Insert	O(n) worst, O(log n) avg	O(log n)	O(log n)
Delete	O(n) worst, O(log n) avg	O(log n)	O(log n)
Traversal	O(n)	O(n)	O(n)

Key Takeaway:
Using a balanced tree (like AVL, Red-Black, or B-Tree) ensures predictable and efficient performance for large-scale applications, while unbalanced trees may degrade to linear time in the worst case if not managed carefully.

Tree Traversal Methods

There are several ways to visit or "traverse" every node in a tree, depending on the order in which nodes are processed. The diagram below summarizes the most common traversal types and some of their typical use cases:

graph TD
    A["Tree Traversal"] --> B["In-Order<br/>Left → Root → Right"]
    A --> C["Pre-Order<br/>Root → Left → Right"]
    A --> D["Post-Order<br/>Left → Right → Root"]
    A --> E["Level-Order<br/>Breadth-first by levels"]

    B --> F["Sorted output for BST"]
    C --> G["Tree copying, expressions"]
    D --> H["Tree deletion, size calculation"]
    E --> I["Level-by-level processing"]

    style A fill:#e3f2fd
    style F fill:#c8e6c9
    style G fill:#c8e6c9
    style H fill:#c8e6c9
    style I fill:#c8e6c9

Binary Search TreesBalanced TreesHeapsTries (Prefix Trees)

A Binary Search Tree (BST) maintains sorted order: left child < parent < right child. This property enables efficient searching, insertion, and deletion.

BST Properties:

• Left subtree contains only values less than root
• Right subtree contains only values greater than root
• Both subtrees are also BSTs
• No duplicate values (typically)

Performance:

• Search: O(log n) average, O(n) worst case
• Insert: O(log n) average, O(n) worst case
• Delete: O(log n) average, O(n) worst case

In production, developers use optimized library implementations rather than hand-rolled BST code. Modern standard libraries provide self-balancing variants (Red-Black Trees, Splay Trees) that guarantee logarithmic performance and handle edge cases automatically. The examples below demonstrate practical BST usage through each language's collection APIs.

JavaKotlinTypeScriptDartSwiftPython

import java.util.TreeMap;
import java.util.TreeSet;

public class BSTExample {
    public static void main(String[] args) {
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(3, "Three");
        treeMap.put(1, "One");
        treeMap.put(2, "Two");

        treeMap.forEach((key, value) -> 
            System.out.println(key + ": " + value));

        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(3);
        treeSet.add(1);
        treeSet.add(2);

        System.out.println("Sorted set: " + treeSet);
    }
}

import java.util.TreeMap
import java.util.TreeSet

fun main() {
    val treeMap = TreeMap<Int, String>()
    treeMap[3] = "Three"
    treeMap[1] = "One"
    treeMap[2] = "Two"

    treeMap.forEach { (key, value) -> 
        println("$key: $value") 
    }

    val treeSet = TreeSet<Int>()
    treeSet.addAll(listOf(3, 1, 2))

    println("Sorted set: $treeSet")
}

import { BinarySearchTree } from 'data-structure-typed';

const bst = new BinarySearchTree<number>();

bst.insert(3);
bst.insert(1);
bst.insert(2);

console.log('Search 2:', bst.search(2));

bst.inOrderTraverse((value) => console.log(value));

console.log('All values:', bst.toArray());

import 'dart:collection';

void main() {
  final treeMap = SplayTreeMap<int, String>();
  treeMap[3] = 'Three';
  treeMap[1] = 'One';
  treeMap[2] = 'Two';

  treeMap.forEach((key, value) => 
      print('$key: $value'));

  final treeSet = SplayTreeSet<int>();
  treeSet.addAll([3, 1, 2]);

  print('Sorted set: $treeSet');
}

import Foundation

struct BSTExample {
    private var elements: [Int] = []

    mutating func insert(_ value: Int) {
        elements.append(value)
        elements.sort()
    }

    func search(_ value: Int) -> Bool {
        return elements.binarySearch(value) != nil
    }

    func inOrderTraversal() -> [Int] {
        return elements.sorted()
    }
}

var bst = BSTExample()
bst.insert(3)
bst.insert(1)
bst.insert(2)

print("Search 2:", bst.search(2))
print("In-order:", bst.inOrderTraversal())

from sortedcontainers import SortedDict, SortedSet

tree_dict = SortedDict()
tree_dict[3] = "Three"
tree_dict[1] = "One"
tree_dict[2] = "Two"

for key, value in tree_dict.items():
    print(f"{key}: {value}")

tree_set = SortedSet([3, 1, 2])
print(f"Sorted set: {tree_set}")

print(f"Search 2: {2 in tree_set}")

Balanced trees maintain logarithmic height to guarantee O(log n) performance for all operations.

Common Types:

• AVL Trees: Strictly balanced by reorganizing nodes when the tree becomes unbalanced. Height difference between left and right subtrees is at most 1. Best for search-heavy operations but requires more reorganization on inserts/deletes.

• Red-Black Trees: Less strict balancing using node colors (red/black). Faster insertions and deletions than AVL with slightly slower searches.

• B-Trees: Multi-way trees where each node has many children instead of just two. Designed for databases and file systems to minimize disk reads by storing more data per node.

Balancing Benefits:

• Guaranteed O(log n) height
• Consistent performance across all operations
• Prevents worst-case O(n) behavior

Most languages implement balanced trees as part of their core collections, using Red-Black Trees or similar self-balancing variants under the hood. These implementations expose additional operations beyond basic BST functionality—like floor/ceiling queries and efficient range searches—making them invaluable for ordered data access patterns in production systems.

JavaKotlinTypeScriptDartSwiftPython

import java.util.TreeMap;
import java.util.concurrent.ConcurrentSkipListMap;

public class BalancedTreeExample {
    public static void main(String[] args) {
        // TreeMap uses Red-Black Tree (balanced)
        TreeMap<Integer, String> balancedTree = new TreeMap<>();

        // Insert elements
        balancedTree.put(5, "Five");
        balancedTree.put(2, "Two");
        balancedTree.put(8, "Eight");
        balancedTree.put(1, "One");
        balancedTree.put(9, "Nine");

        // All operations are O(log n)
        System.out.println("Floor of 7: " + balancedTree.floorKey(7));
        System.out.println("Ceiling of 3: " + balancedTree.ceilingKey(3));

        // Range queries
        System.out.println("Range [2, 8]: " + 
            balancedTree.subMap(2, true, 8, true));
    }
}

import java.util.TreeMap

fun main() {
    // TreeMap uses Red-Black Tree (balanced)
    val balancedTree = TreeMap<Int, String>()

    // Insert elements
    balancedTree[5] = "Five"
    balancedTree[2] = "Two"
    balancedTree[8] = "Eight"
    balancedTree[1] = "One"
    balancedTree[9] = "Nine"

    // All operations are O(log n)
    println("Floor of 7: ${balancedTree.floorKey(7)}")
    println("Ceiling of 3: ${balancedTree.ceilingKey(3)}")

    // Range queries
    println("Range [2, 8]: ${balancedTree.subMap(2, true, 8, true)}")
}

import { AVLTree, RedBlackTree } from 'data-structure-typed';

// Using AVL Tree (height-balanced)
const avlTree = new AVLTree<number>();
avlTree.insert(5);
avlTree.insert(2);
avlTree.insert(8);
avlTree.insert(1);
avlTree.insert(9);

console.log('Height:', avlTree.getHeight());
console.log('Is balanced:', avlTree.isBalanced());

// Using Red-Black Tree
const rbTree = new RedBlackTree<number>();
rbTree.insert(5);
rbTree.insert(2);
rbTree.insert(8);

console.log('Search 5:', rbTree.search(5));
console.log('In-order:', rbTree.inOrderTraverse());

import 'dart:collection';

void main() {
  // Using SplayTreeMap (self-balancing)
  final balancedTree = SplayTreeMap<int, String>();

  // Insert elements
  balancedTree[5] = 'Five';
  balancedTree[2] = 'Two';
  balancedTree[8] = 'Eight';
  balancedTree[1] = 'One';
  balancedTree[9] = 'Nine';

  // All operations are O(log n) amortized
  print('Floor of 7: ${balancedTree.keys.lastWhere((k) => k <= 7)}');
  print('Ceiling of 3: ${balancedTree.keys.firstWhere((k) => k >= 3)}');

  // Range queries
  final range = balancedTree.entries
      .where((e) => e.key >= 2 && e.key <= 8)
      .toList();
  print('Range [2, 8]: $range');
}

import Foundation

// Using Foundation's Set with custom ordering
struct BalancedTreeExample {
    private var elements: SortedSet<Int> = []

    mutating func insert(_ value: Int) {
        elements.insert(value)
    }

    func search(_ value: Int) -> Bool {
        return elements.contains(value)
    }

    func floor(_ value: Int) -> Int? {
        return elements.last(where: { $0 <= value })
    }

    func ceiling(_ value: Int) -> Int? {
        return elements.first(where: { $0 >= value })
    }

    func inOrderTraversal() -> [Int] {
        return Array(elements)
    }
}

var balancedTree = BalancedTreeExample()
balancedTree.insert(5)
balancedTree.insert(2)
balancedTree.insert(8)
balancedTree.insert(1)
balancedTree.insert(9)

print("Floor of 7:", balancedTree.floor(7) ?? "None")
print("Ceiling of 3:", balancedTree.ceiling(3) ?? "None")
print("In-order:", balancedTree.inOrderTraversal())

from sortedcontainers import SortedDict
import bintrees

# Using SortedDict (Red-Black Tree implementation)
balanced_dict = SortedDict()
balanced_dict[5] = "Five"
balanced_dict[2] = "Two"
balanced_dict[8] = "Eight"
balanced_dict[1] = "One"
balanced_dict[9] = "Nine"

# All operations are O(log n)
print(f"Floor of 7: {balanced_dict.bisect_left(7) - 1}")
print(f"Ceiling of 3: {balanced_dict.bisect_right(3)}")

# Range queries
range_items = list(balanced_dict.irange(2, 8))
print(f"Range [2, 8]: {range_items}")

# Using bintrees library for AVL Tree
avl_tree = bintrees.AVLTree()
avl_tree[5] = "Five"
avl_tree[2] = "Two"
avl_tree[8] = "Eight"

print(f"AVL Tree height: {avl_tree.height()}")
print(f"Search 5: {5 in avl_tree}")

A Heap is a specialized tree-based data structure that satisfies the heap property. It's typically implemented as a complete binary tree where each parent node has a specific relationship with its children.

Heap Properties:

• Max-Heap: Parent nodes are greater than or equal to their children
• Min-Heap: Parent nodes are less than or equal to their children
• Complete Binary Tree: All levels are filled except possibly the last level
• Efficient Operations: O(log n) insertion and deletion, O(1) peek

Common Applications:

• Priority queues and task scheduling
• Heapsort algorithm
• Graph algorithms (Dijkstra's shortest path)
• Memory management and garbage collection

Heaps shine in scenarios requiring efficient priority management. Rather than implementing the underlying array-based heap structure manually, developers typically use priority queue implementations provided by standard libraries. These wrappers handle the complex sift-up and sift-down operations internally, exposing a clean API for inserting elements and extracting the minimum (or maximum) value.

JavaKotlinTypeScriptDartSwiftPython

import java.util.PriorityQueue;
import java.util.Collections;

public class HeapExample {
    public static void main(String[] args) {
        // Min-heap (default)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(3);
        minHeap.offer(1);
        minHeap.offer(4);
        minHeap.offer(1);
        minHeap.offer(5);

        System.out.println("Min-heap: " + minHeap);
        System.out.println("Peek (min): " + minHeap.peek());
        System.out.println("Poll (remove min): " + minHeap.poll());

        // Max-heap using reverse order
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.offer(3);
        maxHeap.offer(1);
        maxHeap.offer(4);
        maxHeap.offer(1);
        maxHeap.offer(5);

        System.out.println("Max-heap: " + maxHeap);
        System.out.println("Peek (max): " + maxHeap.peek());

        // Custom objects with priority
        PriorityQueue<Task> taskQueue = new PriorityQueue<>((a, b) -> 
            Integer.compare(a.priority, b.priority));
        taskQueue.offer(new Task("High Priority", 1));
        taskQueue.offer(new Task("Low Priority", 3));
        taskQueue.offer(new Task("Medium Priority", 2));

        while (!taskQueue.isEmpty()) {
            System.out.println("Processing: " + taskQueue.poll().name);
        }
    }

    static class Task {
        String name;
        int priority;

        Task(String name, int priority) {
            this.name = name;
            this.priority = priority;
        }
    }
}

import java.util.PriorityQueue
import java.util.Collections

fun main() {
    // Min-heap (default)
    val minHeap = PriorityQueue<Int>()
    minHeap.offer(3)
    minHeap.offer(1)
    minHeap.offer(4)
    minHeap.offer(1)
    minHeap.offer(5)

    println("Min-heap: $minHeap")
    println("Peek (min): ${minHeap.peek()}")
    println("Poll (remove min): ${minHeap.poll()}")

    // Max-heap using reverse order
    val maxHeap = PriorityQueue<Int>(Collections.reverseOrder())
    maxHeap.offer(3)
    maxHeap.offer(1)
    maxHeap.offer(4)
    maxHeap.offer(1)
    maxHeap.offer(5)

    println("Max-heap: $maxHeap")
    println("Peek (max): ${maxHeap.peek()}")

    // Custom objects with priority
    data class Task(val name: String, val priority: Int)

    val taskQueue = PriorityQueue<Task> { a, b -> a.priority.compareTo(b.priority) }
    taskQueue.offer(Task("High Priority", 1))
    taskQueue.offer(Task("Low Priority", 3))
    taskQueue.offer(Task("Medium Priority", 2))

    while (taskQueue.isNotEmpty()) {
        println("Processing: ${taskQueue.poll().name}")
    }
}

import { MinHeap, MaxHeap } from 'data-structure-typed';

// Min-heap
const minHeap = new MinHeap<number>();
minHeap.add(3);
minHeap.add(1);
minHeap.add(4);
minHeap.add(1);
minHeap.add(5);

console.log('Min-heap size:', minHeap.size);
console.log('Peek (min):', minHeap.peek());
console.log('Poll (remove min):', minHeap.poll());

// Max-heap
const maxHeap = new MaxHeap<number>();
maxHeap.add(3);
maxHeap.add(1);
maxHeap.add(4);
maxHeap.add(1);
maxHeap.add(5);

console.log('Max-heap size:', maxHeap.size);
console.log('Peek (max):', maxHeap.peek());

// Custom objects with priority
interface Task {
    name: string;
    priority: number;
}

const taskHeap = new MinHeap<Task>((a, b) => a.priority - b.priority);
taskHeap.add({ name: 'High Priority', priority: 1 });
taskHeap.add({ name: 'Low Priority', priority: 3 });
taskHeap.add({ name: 'Medium Priority', priority: 2 });

while (!taskHeap.isEmpty()) {
    const task = taskHeap.poll();
    if (task) {
        console.log('Processing:', task.name);
    }
}

import 'dart:collection';

void main() {
  // Min-heap using SplayTreeSet
  final minHeap = SplayTreeSet<int>();
  minHeap.addAll([3, 1, 4, 1, 5]);

  print('Min-heap: $minHeap');
  print('Peek (min): ${minHeap.first}');
  print('Poll (remove min): ${minHeap.first}');
  minHeap.remove(minHeap.first);

  // Max-heap using SplayTreeSet with reverse order
  final maxHeap = SplayTreeSet<int>((a, b) => b.compareTo(a));
  maxHeap.addAll([3, 1, 4, 1, 5]);

  print('Max-heap: $maxHeap');
  print('Peek (max): ${maxHeap.first}');

  // Custom objects with priority
  class Task {
    final String name;
    final int priority;

    Task(this.name, this.priority);

    @override
    String toString() => 'Task($name, $priority)';
  }

  final taskHeap = SplayTreeSet<Task>((a, b) => a.priority.compareTo(b.priority));
  taskHeap.add(Task('High Priority', 1));
  taskHeap.add(Task('Low Priority', 3));
  taskHeap.add(Task('Medium Priority', 2));

  while (taskHeap.isNotEmpty) {
    final task = taskHeap.first;
    print('Processing: ${task.name}');
    taskHeap.remove(task);
  }
}

import Foundation

// Min-heap implementation using Array
struct MinHeap<T: Comparable> {
    private var heap: [T] = []

    var isEmpty: Bool { heap.isEmpty }
    var count: Int { heap.count }

    func peek() -> T? { heap.first }

    mutating func insert(_ element: T) {
        heap.append(element)
        siftUp(from: heap.count - 1)
    }

    mutating func extractMin() -> T? {
        guard !heap.isEmpty else { return nil }
        if heap.count == 1 { return heap.removeFirst() }

        let min = heap[0]
        heap[0] = heap.removeLast()
        siftDown(from: 0)
        return min
    }

    private mutating func siftUp(from index: Int) {
        let parent = (index - 1) / 2
        if index > 0 && heap[index] < heap[parent] {
            heap.swapAt(index, parent)
            siftUp(from: parent)
        }
    }

    private mutating func siftDown(from index: Int) {
        let left = 2 * index + 1
        let right = 2 * index + 2
        var smallest = index

        if left < heap.count && heap[left] < heap[smallest] {
            smallest = left
        }
        if right < heap.count && heap[right] < heap[smallest] {
            smallest = right
        }

        if smallest != index {
            heap.swapAt(index, smallest)
            siftDown(from: smallest)
        }
    }
}

// Usage example
var minHeap = MinHeap<Int>()
minHeap.insert(3)
minHeap.insert(1)
minHeap.insert(4)
minHeap.insert(1)
minHeap.insert(5)

print("Min-heap size: \(minHeap.count)")
print("Peek (min): \(minHeap.peek() ?? -1)")
print("Extract min: \(minHeap.extractMin() ?? -1)")

// Custom objects with priority
struct Task: Comparable {
    let name: String
    let priority: Int

    static func < (lhs: Task, rhs: Task) -> Bool {
        lhs.priority < rhs.priority
    }
}

var taskHeap = MinHeap<Task>()
taskHeap.insert(Task(name: "High Priority", priority: 1))
taskHeap.insert(Task(name: "Low Priority", priority: 3))
taskHeap.insert(Task(name: "Medium Priority", priority: 2))

while !taskHeap.isEmpty {
    if let task = taskHeap.extractMin() {
        print("Processing: \(task.name)")
    }
}

import heapq
from typing import List, Optional

# Min-heap using heapq module
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 4)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 5)

print(f"Min-heap: {min_heap}")
print(f"Peek (min): {min_heap[0]}")
print(f"Poll (remove min): {heapq.heappop(min_heap)}")

# Max-heap using negative values
max_heap = []
for num in [3, 1, 4, 1, 5]:
    heapq.heappush(max_heap, -num)

print(f"Max-heap (negated): {max_heap}")
print(f"Peek (max): {-max_heap[0]}")
print(f"Poll (remove max): {-heapq.heappop(max_heap)}")

# Custom objects with priority
class Task:
    def __init__(self, name: str, priority: int):
        self.name = name
        self.priority = priority

    def __lt__(self, other):
        return self.priority < other.priority

    def __repr__(self):
        return f"Task({self.name}, {self.priority})"

task_heap = []
heapq.heappush(task_heap, Task("High Priority", 1))
heapq.heappush(task_heap, Task("Low Priority", 3))
heapq.heappush(task_heap, Task("Medium Priority", 2))

while task_heap:
    task = heapq.heappop(task_heap)
    print(f"Processing: {task.name}")

# Using PriorityQueue for cleaner syntax
from queue import PriorityQueue

pq = PriorityQueue()
pq.put((1, "High Priority"))
pq.put((3, "Low Priority"))
pq.put((2, "Medium Priority"))

while not pq.empty():
    priority, task_name = pq.get()
    print(f"Processing: {task_name} (priority: {priority})")

A Trie is a tree-like data structure for storing strings, where each path from root to leaf represents a word. Common prefixes are shared, making it efficient for string operations.

Trie Benefits:

• O(L) time complexity for string operations (L = string length)
• Efficient prefix matching and autocomplete
• Space-efficient for shared prefixes
• Fast string search and insertion

Common Applications:

• Spell checkers and autocomplete
• Word games and puzzles
• Search engine indexing

Tries work best with libraries designed for prefix operations. While some languages have trie-specific libraries, others use simpler approaches like sorted collections for autocomplete functionality. The examples below demonstrate practical patterns for prefix-based string operations in each language.

JavaKotlinTypeScriptDartSwiftPython

import org.apache.commons.collections4.trie.PatriciaTrie;
import java.util.SortedMap;

// Using Apache Commons Collections PatriciaTrie
PatriciaTrie<String> trie = new PatriciaTrie<>();
trie.put("apple", "fruit");
trie.put("app", "application");
trie.put("application", "software");

// Search for exact match
System.out.println("Search 'app': " + trie.containsKey("app"));

// Get all words with prefix
SortedMap<String, String> matches = trie.prefixMap("app");
System.out.println("Words with prefix 'app': " + matches.keySet());

import org.apache.commons.collections4.trie.PatriciaTrie

// Using Apache Commons Collections PatriciaTrie
val trie = PatriciaTrie<String>()
trie["apple"] = "fruit"
trie["app"] = "application"
trie["application"] = "software"

// Search for exact match
println("Search 'app': ${trie.containsKey("app")}")

// Get all words with prefix
val matches = trie.prefixMap("app").keys
println("Words with prefix 'app': $matches")

import { Trie } from 'data-structure-typed';

// Using data-structure-typed library
const trie = new Trie();
trie.add("apple");
trie.add("app");
trie.add("application");

// Search for exact match
console.log("Search 'app':", trie.has("app"));

// Get all words with prefix
const matches = trie.getWords("app");
console.log("Words with prefix 'app':", matches);

import 'package:trie/trie.dart';

// Using trie package
void main() {
  final trie = Trie<String>();
  trie.add('apple', value: 'fruit');
  trie.add('app', value: 'application');
  trie.add('application', value: 'software');

  // Search for exact match
  print('Search app: ${trie.contains('app')}');

  // Get all words with prefix
  final matches = trie.findByPrefix('app');
  print('Words with prefix app: ${matches.map((e) => e.key)}');
}

import SwiftTrie

// Using SwiftTrie package
let trie = Trie<String>()
trie.insert("apple", value: "fruit")
trie.insert("app", value: "application")
trie.insert("application", value: "software")

// Search for exact match
print("Search 'app': \(trie.contains("app"))")

// Get all words with prefix
let matches = trie.findWordsWithPrefix("app")
print("Words with prefix 'app': \(matches)")

from pygtrie import CharTrie

# Using pygtrie library
trie = CharTrie()
trie['apple'] = 'fruit'
trie['app'] = 'application'
trie['application'] = 'software'

# Search for exact match
print(f"Search 'app': {'app' in trie}")

# Get all words with prefix
matches = list(trie.keys(prefix='app'))
print(f"Words with prefix 'app': {matches}")

Tree Applications

Common Use Cases:

• File Systems: Directory structures and file organization
• Database Indexing: B-trees for efficient data retrieval
• Expression Parsing: Syntax trees for compilers
• Decision Making: Decision trees for AI and machine learning
• Autocomplete: Tries for search suggestions

Summary

Trees provide efficient hierarchical data organization with logarithmic performance for most operations. Their recursive nature makes them ideal for divide-and-conquer algorithms, while different tree variants offer specialized optimizations for specific use cases like searching, sorting, and string operations. Using established libraries allows developers to focus on application logic rather than low-level implementation details.