height
The number of edges on the longest path from a tree's root down to a leaf; a node's depth is its number of edges from the root.
In more detail
Search, insert and delete in a search tree all cost O(h), where h is the height, so keeping h small is everything. A balanced tree has height O(log n); a degenerate one has height n minus one. Nodes at the same depth form a level.
Related terms
- balanced tree — A tree kept close to its minimum possible height, O(log n), so that searches never take long paths.
- degenerate tree — A search tree in which every node has only one child, so it is really a linked list with height n minus one.
- AVL tree — A self-balancing binary search tree in which the heights of every node's two subtrees differ by at most one.
- B-tree — A balanced search tree whose nodes each hold many sorted keys and have many children, so the tree is very wide and very shallow.
Taught in
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers
- Binary Search Trees: Search, Insert And Delete — Algorithms & Data Structures for Working Engineers
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers