A binary search tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 19 leaves:

Question

Question

This question was previously asked in

UGC NET Computer Science (Paper 2) July 2018 Paper

Attempt Online

Answer 1

Formula:

L = I (n - 1) + 1

where, L = number of leaf nodes

I = number of internal nodes

n = n - ary tree

Explanation:

L = 19

n = 2 (as given tree is strictly binary tree)

19 = I (2 - 1) + 1

I = 18

Number of internal nodes = 18

Number of leaf nodes = 19

Total number of nodes = 18 + 19 = 37

Tips and Trick:

Number of internal node in a binary tree = number leaves - 1 = 19 - 1

Total nodes = number of leaf nodes + internal node = 19 + 18 = 37

Important Point:

Root node is also a internal node.