[Dart] Binary Search Tree Demo

binary_search_tree.dart

class Node {
  Node? leftChild;
  Node? rightChild;
  late int value;

  Node(int data) {
    value = data;
  }
}

class BinarySearchTree {
  Node? root;
  late int size;

  BinarySearchTree() {
    size = 0;
  }

  /// check whether tree is empty
  bool isEmpty() => root == null ? true : false;

  /// add new Node to BST
  void add(int newItem) {
    Node newNode = Node(newItem);
    if (root == null) {
      root = newNode;
    } else {
      Node? curr = root;
      Node? parent;
      bool isLeftChild = false;

      while (curr != null) {
        parent = curr;
        if (curr.value < newItem) {
          curr = curr.rightChild;
          isLeftChild = false;
        } else {
          curr = curr.leftChild;
          isLeftChild = true;
        }
      }

      /// root cannot be `null`
      if (isLeftChild) {
        parent!.leftChild = newNode;
      } else {
        parent!.rightChild = newNode;
      }
    }
    size += 1;
  }

  /// remove selected data from BST
  int? remove(int data) {
    if (root == null) {
      print('Empty Tree');
      return null;
    } else {
      Node? curr = root;
      Node? parent;
      bool isLeftChild = false;
      while (curr != null) {
        if (curr.value == data) break;

        /// move
        parent = curr;
        if (curr.value < data) {
          curr = curr.rightChild;
          isLeftChild = false;
        } else if (curr.value > data) {
          curr = curr.leftChild;
          isLeftChild = true;
        }
      }
      if (curr == null) {
        throw Exception('There is no data with $data');
      }

      /// removing leaves
      if (parent != null) {
        /// check how many children does parent's child has
        if (curr.leftChild != null && curr.rightChild != null) {
          // 2 child
          // find the curr's rightest-min-child
          Node? rightMinChild = curr.rightChild;
          Node? rightMinParent;

          while (rightMinChild!.leftChild != null) {
            rightMinParent = rightMinChild;
            rightMinChild = rightMinChild.leftChild;
          }
          // link with parent
          if (isLeftChild) {
            parent.leftChild = rightMinChild;
          } else {
            parent.rightChild = rightMinChild;
          }

          /// remove rightest min child's parent's leftChild
          if (rightMinParent != null) {
            /// rightMinChild cannot have more leftChild
            if (rightMinChild.rightChild != null) {
              rightMinParent.leftChild = rightMinChild.rightChild;
            } else {
              rightMinParent.leftChild = null;
            }
            // swap with removed item and the rightest min-value node
            rightMinChild.leftChild = curr.leftChild;
            rightMinChild.rightChild = curr.rightChild;
          }

          /// the rightest min-value node is just a single node
          else {
            rightMinChild.leftChild = curr.leftChild;
          }
        } else if (curr.leftChild != null && curr.rightChild == null) {
          // 1 child - left
          if (isLeftChild) {
            parent.leftChild = curr.leftChild;
          } else {
            parent.rightChild = curr.leftChild;
          }
        } else if (curr.leftChild == null && curr.rightChild != null) {
          // 1 child - right
          if (isLeftChild) {
            parent.leftChild = curr.rightChild;
          } else {
            parent.rightChild = curr.rightChild;
          }
        } else if (curr.leftChild == null && curr.rightChild == null) {
          // 0 child
          if (isLeftChild) {
            parent.leftChild = null;
          } else {
            parent.rightChild = null;
          }
        }
      } else {
        /// removing root node
        if (curr.leftChild != null && curr.rightChild != null) {
          Node? rightMinChild = curr.rightChild;

          while (rightMinChild!.leftChild != null) {
            rightMinChild = rightMinChild.leftChild;
          }

          root = rightMinChild;
          root!.leftChild = curr.leftChild;
        } else if (curr.leftChild != null && curr.rightChild == null) {
          root = curr.leftChild;
        } else if (curr.leftChild == null && curr.rightChild != null) {
          root = curr.rightChild;
        } else {
          root = null;
        }
      }

      size -= 1;
    }
  }

  /// print the whole BST
  void show() {
    if (root == null) {
      print('Empty tree');
    } else {
      StringBuffer stringBuffer = StringBuffer();
      dfs(stringBuffer, root, 0);
      print(stringBuffer);
      print('the size of BST: ${size}\n');
    }
  }

  Node? dfs(StringBuffer strBuf, Node? curr, int treeLevel) {
    if (curr == null) return null;
    strBuf.write(
        "${'-' * treeLevel}${'+' * (treeLevel > 0 ? 1 : 0)}${curr.value}\n");
    if (curr.leftChild != null) dfs(strBuf, curr.leftChild, treeLevel + 1);
    if (curr.rightChild != null) dfs(strBuf, curr.rightChild, treeLevel + 1);
    return curr;
  }
}

void main() {
  BinarySearchTree bst = BinarySearchTree();
  bst.add(3);
  bst.add(4);
  bst.add(6);
  bst.add(2);
  bst.add(1);
  bst.add(10);
  // bst.add(7);
  // bst.add(8);
  bst.add(5);
  // bst.add(9);
  bst.show();
  bst.remove(6);
  bst.remove(3);
  bst.show();
}