2. Recall that in a binary tree, a node may have 0, 1, or 2 children. In the fol

Question

2. Recall that in a binary tree, a node may have 0, 1, or 2 children. In the following questions about binary trees, the height of a tree is the length (number of edges) of the longest path. A tree consisting of just one node has height o. a. What is the maximum number of nodes in a binary tree of height d? b What is the minimum number of no inabinary tree of height d? c. What is the maximum height of a binary tree containing n nodes? d. What is the minimum height of a binary tree containing n nodes?

Explanation / Answer

a. For the maximum number of nodes in a tree with height 'd', we need to place as many nodes as possible in the tree. Since, binary trees have atmost 2 child nodes, we need to form a complete binary tree with all parents having 2 child nodes. And number of nodes in a binary tree in terms of height is 2height+1 -1.

Therefore the answer is 2d+1 -1.

b. For minimum number of nodes in a binary tree with height 'd', we need to place as less of nodes as possible in a binary tree. Since, the minimum number of child nodes a node can have in a BT is zero, but this will not contribute to the height of the BT as there won't be any edges without child nodes.

So, we have to place exactly one child node for every parent node in the BT for the answer.

The resulting tree will have a single branched chain like structure with d+! nodes in it. Ans: d+1.

c. For maximum height of the binary tree with n nodes we need to review the part b of the solution. We need to maximize the height of the tree by increasing its height at every node placed.

The tree will have similar chain like structure as in part b. And the answer is h+1 number of nodes.

d. For minimum height of the binary tree with n nodes, we need to review the part a of the solution. We need to minimise the height of the tree with every node placed. This can be done by placing maximum nodes in the same level itself. Therefore the tree structure will be that of a complete binaty tree.

For the answer, we need to rearrange the expression used in part a:

n = 2d+1 -1

We can say that for every level, i maximum number of nodes is 2i . So, total number of nodes till height 'd' is:

20 +21 + 22 + ... + 2d = 2d+1 -1 <= n   (for maximum nodes.)

The LHS is a logarithmic expansion for: log2(n+1) - 1 (ans)

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.