Optimized binary search tree implementation in C++.

Note: Binary search trees are not balanced by definition. This implementation does not guarantee O(log n) complexity when searching or deleting.


  • Pretty good performance compared to many other implementations on the internet.
  • No recursion except for debugging purposes.
  • Node-based on-delete balancing is supported. If you don’t need it, you can easily disable it.
  • Unique / non-unique element insertion.
  • 2 deletion methods are supported:
    1. With payload copying (efficient, when it’s size is less than 2 * sizeof(void*)).
    2. With pointer rearrangement.
  • Debug tree printing with indentation.
  • Lightweight, only one header file.

Copyright © 2019 — 2023 Alexander Mayorov. All rights reserved.