Trees

BinarySearchTree

BinarySearchTree keeps values ordered with a user-supplied comparator. It exposes traversal helpers (in, pre, post order), search/delete operations, and metrics() for height + node count reporting. The tree is unbalanced, so worst-case operations degrade to O(n).

import { BinarySearchTree, createComparator } from '@avensio/shared'

const tree = new BinarySearchTree(createComparator('id'))
tree.insert({ id: 3 })
tree.insert({ id: 1 })
tree.insert({ id: 5 })

tree.delete({ id: 3 }) // comparator controls equality
tree.traverse('pre')   // traversal order
tree.metrics()         // { height, nodeCount }

• insert(value) – adds a node; duplicates are inserted on the right subtree.
• find(value) – returns the stored value or null.
• delete(value) – removes the node if present and returns a boolean.
• traverse(order?) – returns an array of values in 'in', 'pre', or 'post' order (defaults to in-order).
• min() / max() – fetch extremes in O(log n) average time.
• metrics() – returns { height, nodeCount } so you can track balance and growth.
• [Symbol.iterator] – yields values in-order, making the tree compatible with for...of and spread syntax.

Complexity

Operation	Average	Worst-case
insert	O(log n)	O(n)
find / delete	O(log n)	O(n)
traverse	O(n)	O(n)
min / max	O(log n)	O(n)

Notes

• Use BinaryHeap when you only need fast extracts without ordered traversal.
• Combine trees with Comparator helpers to customize ordering logic.
• For balanced search trees, consider composing this tree with your own rebalancing layer.