Question

If the height of a binary tree is 54, how many null pointers are there as children?

(a) 1267

(b) 3^58

(c) 56

(d) 2^55

The question was asked by my college professor while I was bunking the class.

My question is taken from Recursion topic in division Induction and Recursion of Discrete Mathematics

Answer 1

Correct option is (d) 2^55

The explanation is: Depth-first search (DFS) algorithm of a binary tree, is a trivial example of short-circuiting. We can have a standard recursive algorithm in case of DFS. Now, a perfect binary tree of height h has 2^h+1 Null pointers as children.

h = 54

2^54+1

2^55.