Spread the post

Count internal node of binary search tree using recursion

How to count Binary search tree internal nodes or none leaf nodes ? first we are discuss about that what is internal node of BST. Internal node of binary search tree that are have at least one child node. Look at the view of internal node of binary search tree.

Examples:

Given BST tree node is:

428, 423, 473, 436, 498, 460, 493, 499, 476, 515

View Tree Try it yourself

count internal node

Number of Internal node is : 6

Another Example

Given BST tree node is:

[64, 27, 76, 4, 33, 68, 91, 26, 37, 70, 100 ]

Try it yourself

example count internal node

Internal node of this tree is [7].

Recursive Algorithm

Execution Process

view execution process to count all internal node in given binary search tree.

Given tree

507030902010156080

Execution process

Code Execution Process Code execution process to find all internal node of binary search tree. Stack Areamainresult (int) =6root(pointer)count_internaltemp(pointer)value(pointer)count_internaltemp(pointer)value(pointer) Heap Areastruct Treedata (int)= 50left_child (pointer) right_child (pointer) struct Treedata (int)= 70left_child (pointer) right_child (pointer) struct Treedata (int)= 30left_child (pointer) right_child (pointer)= NULLstruct Treedata (int)= 90left_child (pointer) right_child (pointer)= NULLstruct Treedata (int)= 20left_child (pointer) right_child (pointer)= NULLstruct Treedata (int)= 10left_child (pointer)= NULLright_child (pointer) struct Treedata (int)= 15left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 60left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 80left_child (pointer)= NULLright_child (pointer)= NULL

Below in C implementation of this problem. Recursive approach.

Output
  BST Data is :  10  15  20  30  50  60  70  80  90
 Number of internal node is : [6]   

Spread the post

Recommended Posts: