tsearch method

dynamic tsearch(dynamic key, List rootp, int compar(dynamic, dynamic))

Binary tree search. rootp should be a single-element list holding the root node, or null if empty. If key is found, it is returned. Otherwise, it is inserted and returned.

Implementation

dynamic tsearch(dynamic key, List<dynamic> rootp, int Function(dynamic, dynamic) compar) {
  if (rootp.isEmpty) rootp.add(null);
  if (rootp[0] == null) {
    rootp[0] = _TNode(key);
    return (rootp[0] as _TNode).key;
  }
  _TNode curr = rootp[0];
  while (true) {
    int c = compar(key, curr.key);
    if (c == 0) return curr.key;
    if (c < 0) {
      if (curr.left == null) {
        curr.left = _TNode(key);
        return curr.left!.key;
      }
      curr = curr.left!;
    } else {
      if (curr.right == null) {
        curr.right = _TNode(key);
        return curr.right!.key;
      }
      curr = curr.right!;
    }
  }
}