Data Structures and Algorithms · Trees

Binary search trees

A binary tree kept ordered so each node's left subtree is smaller and right subtree is larger.

Also known as: BST, ordered tree.

Start a lesson on Binary search trees

Learn first

• Binary trees: A hierarchical structure where each node has at most two children.
• Binary search: Repeatedly halving a sorted range to find a target in logarithmic time.

Leads to

• Balanced search trees: A BST that actively rebalances itself, AVL rotations or red-black coloring, so it never degrades into a line.

Related topics

• Balanced search trees: A BST that actively rebalances itself, AVL rotations or red-black coloring, so it never degrades into a line.