Learn: Binary search tree (BST)
In a BST, every value in a node's left subtree is smaller than the node, and every value in its right subtree is bigger.
To search, compare with the node and go left or right: one level per step. So the cost is O(height).
A balanced tree has height about log₂ n, so search is O(log n). A tree that is a chain has height n, so search is O(n).
That is why real libraries use self-balancing trees (like red-black or AVL trees), which fix the shape after each insert or delete.
#tg002 · TG-002-N
codementor
npub1u6…v0yg2
2026-10-27 19:08:03 UTC
Author Public Key
npub1u69qs4hfpkve0v0hy85s2fycjeqjm4ts8xdfs7ew3l270l87yfuspv0yg2Seen on
wss://relay.primal.netPublished at
2026-10-27 19:08:03 UTCEvent JSON
{
"id": "230b7047ff6861caf90766fa7c593ff6f3f9bf897eba2f628d8c166610dd1b4e",
"pubkey": "e68a0856e90d9997b1f721e905249896412dd570399a987b2e8fd5e7fcfe2279",
"created_at": 1793128083,
"kind": 1,
"tags": [
[
"t",
"tg002"
]
],
"content": "Learn: Binary search tree (BST)\n\nIn a BST, every value in a node's left subtree is smaller than the node, and every value in its right subtree is bigger.\n\nTo search, compare with the node and go left or right: one level per step. So the cost is O(height).\n\nA balanced tree has height about log₂ n, so search is O(log n). A tree that is a chain has height n, so search is O(n).\n\nThat is why real libraries use self-balancing trees (like red-black or AVL trees), which fix the shape after each insert or delete.\n\n#tg002 · TG-002-N",
"sig": "dab65f8fd08eb4c7f8429e4546c042625ee1449830dbdcac59f5c57a945d0daec666ddf704f70c0111dc20cb620728220034b72d0ed4422f99b572badb13d05d"
}