AvlTree: insert is O(n) because height/balanceFactor are recomputed recursively (README claims O(log n)) #2235

BinaryTreeNode.height, leftHeight, rightHeight and balanceFactor (lines 25–55) are recursive getters with no caching, and AvlTree.balance() evaluates them on every ancestor. Counting calls to the height getter per insert:

That grows linearly with n, so building a tree is O(n²). Fix: store height on the node and update it on attach and rotation. (Independent of the correctness bugs in #325 and #485.)

Found during an independent property-based audit of this repo (full report and reproducible harness: https://github.com/devladpopov/algorithm-autopsy/tree/main/autopsy-02).