Binary tree algorithms in Dart

binary_tree.dart

import 'dart:math';

class Queue<T> {
  final _items = <T>[];
  void push(T value) {
    _items.add(value);
  }
  
  T pop() {
    return _items.removeAt(0);
  }
  
  int get length => _items.length;
}

class Stack<T> {
  final _items = <T>[];
  void push(T value) {
    _items.add(value);
  }
  
  T pop() {
    return _items.removeLast();
  }
  
  int get length => _items.length;
}

class Node<T> {
  Node(this.value);
  final T value;
  Node<T>? left;
  Node<T>? right;
}

void main() {
  final root = Node(5);
  final left = Node(4);
  final right = Node(6);
  final innerLeft = Node(3);
  final innerRight = Node(7);
  root.left = left;
  root.right = right;
  left.left = innerLeft;
  left.right = innerRight;
  depthFirstSearch(null);
  breadthFirstSearch(root);
  print(recursiveDepthFirstSearch(root));
  print(treeSum(root));
  print('min value: ${minValue(root)}');
}


int minValue(Node<int>? root) {
  if(root == null) return 99999999999;
  final leftMin = minValue(root.left);
  final rightMin = minValue(root.right);
  return [root.value, leftMin, rightMin].reduce(min);
}

/// Breadth first search algorithm
void breadthFirstSearch(Node<int>? root) {
  final queue = Queue<Node>();
  if(root != null) {
    queue.push(root);
  }
  while(queue.length > 0) {
    final current = queue.pop();
    print(current.value);
    if(current.right != null) {
      queue.push(current.right!);
    }
    if(current.left != null) {
      queue.push(current.left!);
    }
  }
}


/// Tree sum algorithm
int treeSum(Node<int>? root) {
  if(root == null) return 0;
  return root.value + (treeSum(root.left) + treeSum(root.right));
}


/// Depth first search
void depthFirstSearch(Node<int>? root) {
  final stack = Stack<Node>();
  if(root != null) {
    stack.push(root);
  }
  while(stack.length > 0) {
    final current = stack.pop();
    print(current.value);
    if(current.right != null) {
      stack.push(current.right!);
    }
    if(current.left != null) {
      stack.push(current.left!);
    }
  }
}

List<int> recursiveDepthFirstSearch(Node<int>? root) {
  if(root == null) return [];
  final leftItems = recursiveDepthFirstSearch(root.left);
  final rightItems = recursiveDepthFirstSearch(root.right);
  return [root.value, ...leftItems, ...rightItems];
}