Trees
Hierarchies, balancing & queries
Binary Search Tree
Ordered tree where every left subtree is smaller and every right subtree larger — insert, search and delete all follow one root-to-leaf path.
Time O(h) · Space O(n)
AVL Tree
A self-balancing BST: after each insert it checks balance factors and rotates so the height stays O(log n).
Time O(log n) · Space O(n)
Binary Heap
A complete binary tree stored in an array; push sifts a value up and pop sinks the last element down to restore the max-heap order.
Time O(log n) · Space O(n)
Trie (Prefix Tree)
A tree keyed by characters: each root-to-node path spells a prefix, so insert and lookup cost only the length of the word.
Time O(L) · Space O(Σ · N)
Segment Tree
A binary tree over array ranges: each node stores an aggregate (here, a sum) so range queries resolve in O(log n) by combining O(log n) covering nodes.
Time O(log n) query · Space O(n)