To prove that the minimum height of an $n$-vertex binary tree is equal to $\left\lceil \log_2(n + 1) - 1 \right\rceil$, we will proceed step by step:

Step 1: Definition of a Binary Tree Height

• Height of a binary tree is defined as the number of edges on the longest path from the root to a leaf node.
• For an $n$-vertex binary tree, we have $n$ nodes, and we are interested in finding the minimum height of such a tree.

Step 2: Full Binary Tree and Minimum Height

• A full binary tree is a binary tree where every node has either 0 or 2 children.
• The minimum height occurs when the tree is as "balanced" as possible, meaning each level of the tree is fully populated before the next level starts.

Step 3: Relationship Between Nodes and Height

• In a full binary tree of height $h$, the number of vertices $n$ is given by the formula: $n = 2^{h+1} - 1$ where $h$ is the height of the tree, and the tree is fully populated at each level.

Step 4: Estimating Minimum Height

• To find the minimum height for a binary tree with $n$ nodes, we need to ensure that we use as few levels as possible while still containing all $n$ nodes.

• A complete binary tree is one where all levels, except possibly the last, are completely filled, and all nodes are as far left as possible. The minimum height of such a tree can be derived by recognizing that the number of nodes $n$ fits within a tree whose height is related to $\log_2(n)$.

Step 5: Derivation of the Minimum Height Formula

• For a binary tree to contain at least $n$ nodes, the height $h$ of the tree must satisfy: $2^h - 1 \leq n \leq 2^{h+1} - 1$ The first inequality ensures that the tree has enough nodes to reach a certain height, and the second inequality ensures that it doesn't exceed the number of nodes in the next higher level.

• Solving for $h$, we get: $h = \left\lceil \log_2(n + 1) - 1 \right\rceil$ This expression gives the minimum height of the binary tree with $n$ nodes.

Step 6: Final Result

Therefore, the minimum height of an $n$-vertex binary tree is given by: $\boxed{\left\lceil \log_2(n + 1) - 1 \right\rceil}$

---

Would you like further details on this derivation, or any specific step explained more clearly?

Here are five related questions you might explore:

1. What is the maximum height of a binary tree with $n$ nodes?
2. How does the number of nodes in a full binary tree relate to its height?
3. What is the difference between a complete binary tree and a full binary tree?
4. How does balancing affect the height of a binary tree?
5. Can a binary tree have height $\lceil \log_2(n + 1) - 1 \rceil$ without being complete?

Tip: Understanding the structure of full and complete binary trees is key when analyzing tree heights and node distributions.