CODEWITHSUNDEEP
data-structuresbinary-tree
Ankur Lathiya
Ankur Lathiya

Reputation: 174

How to find internal nodes in binary tree?

I already got the method to find external nodes but I have no idea about to count internal nodes so someone please help.

Upvotes: 1

Views: 1969

Answers (2)

adijo
adijo

Reputation: 1580

You could convert the following pseudocode to any language as per your preference. 

function count_internal_nodes(curr):
       if curr == null: return 0
       else if curr is leaf: return 0
       else: return 1 + count_internal_node(curr.left) + 
                        count_internal_nodes(curr.right)

Upvotes: 2

Rahul Tripathi
Rahul Tripathi

Reputation: 172618

You can try this algo

getInteriorNodes(self)
    count = 0
    hasLeft, hasRight = self.left<>null, self.right <>null
    if (hasLeft)
        count += self.left.getInteriorNodes()
    else if (hasRight)
        count += self.right.getInteriorNodes()
    else if ((hasLeft || hasRight) && self.parent) 
        count += 1
 return count

Upvotes: 0

Related Questions