△ Binary Trees
06 — Data Structures
Hierarchical data — O(log n) search

Binary Trees

Every node has at most two children. Keep it sorted as a BST and each comparison throws away half the tree — that is the power of O(log n).

A binary tree is a hierarchy where each node has at most a left and right child, and one parent. The top node is the root; nodes with no children are leaves. A Binary Search Tree (BST) adds one rule: everything in a node's left subtree is smaller, everything in its right subtree is larger. That ordering lets a search discard half the remaining nodes at every step — halving the problem each time gives O(log n), as long as the tree stays balanced.

Try it in 3D

Each orb is a node; left is always smaller, right always larger. Drag to orbit. Search and watch comparisons eliminate whole subtrees.

Drag to rotate — scroll to zoom
Press an operation above.ready
Comparing Found / Inserted In-order visit Cursor

The operations

Each comparison halves the remaining nodes — as long as the tree stays reasonably balanced.

Cost cheat sheet

Balanced vs unbalanced changes everything. Insert sorted data and a BST degrades to O(n).