Part 1 The depth of a vertex in a rooted tree is defined to be the number of edg
ID: 2986904 • Letter: P
Question
Part 1
The depth of a vertex in a rooted tree is defined to be the number of edges on the unique path to the root. The height of a rooted tree is the maximum of the depths of its vertices. A binary tree is complete if it is full and all its leaves have the same depth.
a) How many vertices does a complete binary tree of height 1 have?
b) Height 2?
Proof required for height d.
Part 2
As defined above, a binary tree is complete if it is full and all its leaves have the same depth. A vertex that is not a leaf vertex is called an internal vertex What is the relationship between the number I of internal vertices and the number L of leaf vertices in a complete binary tree?
Explanation / Answer
a) 1 + 2 = 3
b) 1 + 2 + 4 = 7
c) 1 + 2 + 2^2 + 2^3 + . . . . 2^(d-1) + 2^d
This is a GP with a = 1, r = 2, n = d+1
Sum = a*(r^n - 1) / (r-1) = 1*(2^(d+1) - 1) / (2-1) = 2^(d+1) - 1
d) No. of internal vertices of a complete binary tree of height d = 1 + 2 + 2^2 + . . . 2^(d-1)
=> I = 2^d - 1
No. of leaves in complete binary tree of height d = 2^d
=> L = 2^d
Hence, L = I + 1