Discrete Math Multiple Choice Let T be a full binary tree wi

Discrete Math Multiple Choice:

Let T be a full binary tree with k internal vertices. What is the number of terminal vertices for T?

A. 2K+1

B. 2K

C. 2K-1

D. k+2

Solution

A rooted tree is said to be a binary tree is if each vertex has at most two children ( left child and right child). If a vertex has one child, that child is designated as either a left child or a right child, but not both.

A binary tree is said to be a full binary tree if each vertex has exactly two children or none. A vertex of degree 1 is called a terminal vertex and a vertex of degree greater than 1 is called an internal vertex.

If T is a full binary tree with k internal vertices, then T has k+1 terminal vertices and 2k + 1 total vertices.