A full binary tree with n leaf nodes has in all ______ nodes.
2015
A full binary tree with n leaf nodes has in all ______ nodes.
- A.
2n - 1
- B.
2n
- C.
2n + 1
- D.
log 2n
- E.
Question not attempted
Attempted by 853 students.
Show answer & explanation
Correct answer: A
In a full binary tree, every internal node has exactly two children. Let the number of leaf nodes be n.
Step 1: The number of internal nodes in a full binary tree is always one less than the number of leaf nodes. So, internal nodes = n - 1.
Step 2: Total number of nodes = leaf nodes + internal nodes = n + (n - 1) = 2n - 1.
Therefore, a full binary tree with n leaf nodes has 2n - 1 nodes in total.
हिन्दी उत्तर:
एक पूर्ण द्विआधारी वृक्ष में, प्रत्येक आंतरिक नोड के ठीक दो बच्चे होते हैं। मान लीजिए कि पर्ण आसंधियों की संख्या n है।
चरण 1: पूर्ण द्विआधारी वृक्ष में आंतरिक नोडों की संख्या पर्ण आसंधियों की संख्या से एक कम होती है। इसलिए, आंतरिक नोड = n - 1।
चरण 2: कुल नोड = पर्ण आसंधियाँ + आंतरिक नोड = n + (n - 1) = 2n - 1।
इसलिए, n पर्ण आसंधियों वाले पूर्ण द्विआधारी वृक्ष में कुल 2n - 1 आसंधियाँ होती हैं।