How to Answer: A binary tree is of height K and has N leaf nodes on it. What are the maximum and minimum possible values of N in terms of K? Would your answer be any different if the tree was a binary search tree?
Advice and answer examples written specifically for a Java Beginner Level Algorithms job interview.
2. A binary tree is of height K and has N leaf nodes on it. What are the maximum and minimum possible values of N in terms of K? Would your answer be any different if the tree was a binary search tree?
This question tests your understanding of trees in general, and the binary search tree structure in relation to its use.
A binary tree (or any tree for this case) of height K can have as few as K+1 nodes with only one of them a leaf. This is the case that the tree is in the shape of a linked list - all of its nodes but the single leaf have exactly one child. So, the minimum possible value of N is 1, regardless of the value of K.
A tree of specific height has maximum number of leaf nodes when it is full, i.e. all of its tree levels have as many nodes as there can be. A binary tree of height K has K+1 levels, with the root node at the top level.
On a full tree, every node except the leaves have 2 child nodes. When this is the case, the number of nodes are doubled from one level to the next-- root is the only node at level-0, level-1 has 2 nodes, .. level-K has 2*K nodes. The maximum possible number of leaf nodes on a binary tree of height K is 2*K.
The answer wouldn't change for the binary search tree structure. The updates on a binary search tree do not impose any limitations on its structure. The two extreme cases described above can occur in binary search trees as well.
Written by Ryan Brown on May 17th, 2021