Tree height

As explained in Grokking Data Structures

Tree height is the length of the longest path from a tree's root to any leaf, measured in edges or levels according to the chosen convention.

Think of a tree as branching paths from a starting point. Its height is the length of the longest path from the root to any leaf, counted in links. section 11.2

Height also tells you how many levels a tree reaches: level 0 contains the root, level 1 its children, and so on. In a binary heap with n elements, the height grows as O(log n). section 10.11

A path and a subtree

A path such as 0→2→6→3 contains three links, so a tree with that longest path has height 3. The subtree rooted at 8 has height 2. section 11.2

Height strongly affects binary-search-tree performance. Searching follows one root-to-leaf path and takes O(h) comparisons; an unbalanced tree can reach height n, while a balanced tree keeps height O(log n). section 11.17 section 11.8

Visualizes how sorted insertion sequences produce completely skewed trees and maximum height. section 11.17

How Grokking Data Structures covers it

How deep it goes

Defines height with paths and levels, applies it to performance, and defers the mathematical derivation of logarithmic growth.

Examples

Uses a three-link path, a height-two subtree, heap levels, and sorted insertions that create skewed binary search trees.

What it assumes

Defines roots, leaves, paths, children, ancestors, descendants, and subtrees before applying the metric.

What you can do after

Evaluate tree shape and estimate search, insertion, deletion, and related operation costs from the height.

How it connects

Connects tree height with binary trees, heaps, binary search trees, balanced trees, paths, roots, leaves, and subtrees.

liveBookmanning.com

Read Grokking Data Structures on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Advanced Algorithms and Data StructuresTree height is the number of edges on the longest path from a tree's root to a leaf.
• 

  liveBookmanning.com
  Grokking Algorithms, Second EditionTree height is the maximum number of edges or steps on a downward path from the root to a leaf or other node.

Compare how 3 books explain tree height →

Related concepts

• branching factorconfigured by · A branching factor is the number of successor nodes or choices available from a node, commonly represented by a maximum or average value.
• treemeasures · A tree is a connected, acyclic structure of nodes, commonly organized hierarchically through parent-child relationships and optionally around a designated root.
• treapused by · A treap is a randomized binary search tree whose nodes satisfy both binary-search-tree ordering by key and heap ordering by priority.
• heapmeasures · A binary heap is an almost complete binary tree in which each parent satisfies an ordering property relative to its children, enabling efficient access to a minimum or maximum element.

This explainer was generated by Manning's knowledge graph from the text of Grokking Data Structures. The section links point to the parts of the book it draws on.