Programming and data structure miscellaneous

Programming and data structure miscellaneous

Easy Questions

Programming & Data Structure

Programming and data structure miscellaneous
  1. The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is








  1. View Hint View Answer Discuss in Forum

    This is a formula to calculate the total number of nodes. It is 2n + 1 – 1.
    Let consider some examples to prove this.
    1. Simplest could be taking the binary tree of h (height) = 0.
    Now, the binary tree of height h will have only 1 node.

    Using formula 2 ^ (0 + 1) – 1 = 1. Hence, the formula is correct.
    2. Binary tree of h (height) = 2

    Using formula 2 ^ (2 + 1) – 1 = 7. Hence, the formula is correct.

    Correct Option: C

    This is a formula to calculate the total number of nodes. It is 2n + 1 – 1.
    Let consider some examples to prove this.
    1. Simplest could be taking the binary tree of h (height) = 0.
    Now, the binary tree of height h will have only 1 node.

    Using formula 2 ^ (0 + 1) – 1 = 1. Hence, the formula is correct.
    2. Binary tree of h (height) = 2

    Using formula 2 ^ (2 + 1) – 1 = 7. Hence, the formula is correct.

  1. The maximum number of binary trees that can be formed with three unlabelled nodes is








  1. View Hint View Answer Discuss in Forum

    It is given that n = 3

    1
    		 2nCn
    n + 1

    1
    		 6C3
    3 + 1

    1.6!
    		 = 5
    4 × 3!3!

    Therefore, there are 5 trees that can be formed with three unlabelled node.

    Correct Option: B

    It is given that n = 3

    1
    		 2nCn
    n + 1

    1
    		 6C3
    3 + 1

    1.6!
    		 = 5
    4 × 3!3!

    Therefore, there are 5 trees that can be formed with three unlabelled node.

  1. A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. The root is stored at X[1].For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any in X[2i | 1]. To be able to store any binary tree on n vertices the minimum size of X should be








  1. View Hint View Answer Discuss in Forum

    For a right skewed binary tree, number of nodes will be 2^ (n – 1). For example, in below binary tree, node 'A' will be stored at index 1, 'B' at index 3, 'C' at index 7 and 'D' at index 15.

    Correct Option: D

    For a right skewed binary tree, number of nodes will be 2^ (n – 1). For example, in below binary tree, node 'A' will be stored at index 1, 'B' at index 3, 'C' at index 7 and 'D' at index 15.

  1. You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this ?








  1. View Hint View Answer Discuss in Forum

    To construct a BST from post order we also require in-order traversal since given the elements are 1 2.......n. So their sorted order would be in order. Using both BST can be constructed in a linear scan. So it will take only 4n time.

    Correct Option: B

    To construct a BST from post order we also require in-order traversal since given the elements are 1 2.......n. So their sorted order would be in order. Using both BST can be constructed in a linear scan. So it will take only 4n time.

  1. In a binary tree with n nodes, every node has an odd number of descendant. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child ?








  1. View Hint View Answer Discuss in Forum

    Such a binary tree is full binary tree (a binary tree where every node has 0 or 2 children).

    Correct Option: A

    Such a binary tree is full binary tree (a binary tree where every node has 0 or 2 children).