Number of articulation points in a full binary tree


#1

A vertex is an articulation point if and only if removing it disconnects the graph. A full binary tree is one in which every node has 0 o 2 children. Number of articulation points in a full binary tree with n nodes is ?

A. n/2
B. n-1
C. (n+1)/2
D. (n-1)/2


#2

Just Remember one important formula here,

X = L(N-1) +1

X -> No. of internal nodes
L -> No. of leaf nodes
N -> value of ‘N’ of any N-ary tree.

In the given question it is simply asking to find the Total number of internal nodes in the binary tree because if you delete any internal node of a binary tree then it will split the graph into 2 parts or disconnect the graph.

Binary tree is a 2-ary Tree.
So N=2.

Putting in equation,
X = L(2-1) + 1
X = L + 1 ------> eqn (i)

Now we can form another equation from the data given in the question,
It’s given that there are total ‘n’ nodes.

So, No. of internal nodes + No. of Leaf nodes = n

-> X + L = n ---------> eqn (ii)

Solving eqn (i) & (ii) for the value of ‘X’,

we get,
X = (n+1)/2

So option C is the correct answer.