if a binary tree has height 5, what is the maximum number of leaves it can have?
if a binary tree has height 5, what is the maximum number of leaves it can have?
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
Based on Theorem 4.4.1 P.163, if a binary tree has height 5, what is the maximum number of leaves it can have?

Transcribed Image Text:4.4 Binary Trees with (at Least) n! Leaves
163
4.4 Binary Trees with (at Least) n! Leaves
A Binary Tree is a tree T with a certain distinguished vertex, r, called the root of
T and placed at the top of the diagram, and where each vertex, v, of T has at most
two vertices directly below it in the diagram.
A leaf is a vertex with no vertices below it; the other (non-leaf) vertices are
known as internal vertices. For any vertex, v, there is a unique path from it back to
the root r.
// up the diagram and down the tree
The length of that path is the number of edges traversed and is called the height of
vertex v and denoted by h(v).
The height of the tree T equals the height of the highest vertex in T.
// so h(r) = 0
%3D
// the highest leaf
Theorem 4.4.1: A Binary Tree with height h has at most 2" leaves.
Proof. I/ by Strong Induction on h where h e {0.. }
Step 1. If T has height h = 0, there can be no vertex in J other than the root, r.
Then, r must be a leaf and so T has exactly 1 = 2" leaves.
Step 2. Assume 3q >= 0 such that for any k where 0 <= k <= q,
any Binary Tree with height k has at most 2* leaves.
Step 3. Suppose T* is some particular Binary Tree with height q + 1 rooted at
vertex r.
// We must prove that T* has at most 2ª+1
leaves.
Expert Solution

This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps

Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you

Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education

Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON

Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON

Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education

Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON

Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON

C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON

Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning

Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education