Last updated Unknown

Status: Tags: #archivedCards/macm101/induction Links: Mathematical Induction

Structural Induction

• Height of binary tree, h(T)
• Recursive definition:
  • Basis step: Height of a single vertex r is 0, h(r) = 0
  • Inductive step: Tree T is built from trees $T_1$, $T_2$ as shown in inductive step, h(T) = 1 + max of $T_1$, $T_2$

Prove Rooted Tree using mathematical induction ?

• Basis case: Single vertex is binary tree
• 

Proving number of vertices in a binary tree, n(T), satisfied equality n(T) <= $2^{h(T)+1}$ - 1 ?

Backlinks

1

list from Structural Induction AND !outgoing(Structural Induction)

References:

Created:: 2021-11-04 09:04