Question

Design a recursive algorithm that determines whether the number of leaf nodes of a Binary Search Tree (BST) is even or odd. An empty tree has an even number of leaves. A tree consisting of just a root has an odd number of leaves. Your function should return true for an even number of leaves, and false for an odd number of leaves. Analyze the execution time of your algorithm. Giving only the execution time without explanation will not be considered a valid answer.

Answer 1

`Hey,

Note: If you have any queries related to the answer please do comment. I would be very happy to resolve all your queries.

Here is an algorithm to get the leaf node count.

getLeafCount(node)
1) If node is NULL then return 0.
2) Else If left and right child nodes are NULL return 1.
3) Else recursively calculate leaf count of the tree using below formula.
    Leaf count of a tree = Leaf count of left subtree + 
                                 Leaf count of right subtree

checkEvenOrOdd(node)

1) If getLeafCount(node)%2==0 then RETURN EVEN ELSE RETURN ODD

Execution time is O(h)=O(n)

Kindly revert for any queries

Thanks.