A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{ no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x } then the worst-case time complexity of the program is

The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always tree?

A complete n-ary tree is one in which every node has O or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by