Data Structures and Algorithms - Trees

26. If the post-order traversal gives a b - c d * + then the label of the nodes 1, 2, 3 ... will be

tree

  • Option : A
  • Explanation : Post-order traversal yields 4, 5, 2, 6, 7, 3, 1. Comparing with a, b, -, c, d, *, +, we get the labels of nodes 1, 2, 3, 4, 5, 6, 7 ans +, -, *, a, b, c, d respectively.
Cancel reply
Cancel reply

27. Consider the following tree

  • Option : D
  • Explanation : If it is to be used for sorting label of left child should be less than the label of the current node. Coming down the tree we get left child of node labeled 10 as the correct slot for 8.
Cancel reply
Cancel reply

28. The number of possible ordered trees with 3 nodes A, B, C is

  • Option : B
  • Explanation : It is 12. The tree may be of depth 2 or 1. if the depth is 2, we have 6 possible trees. This is because one of the three nodes A, B, C may be the root and the next level may be one of the remaining two nodes. If the depth is 1, the root may be one of the 3 nodes A, B, C. Corresponding to a root, say A, two trees as possible as this.
Cancel reply
Cancel reply

29. A binary tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 10 leaves

  • Option : B
  • Explanation : A strictly binary tree with 'n' leaves must have (2n-1) nodes. Verify for some small 'n'. This can be proved by the principle of mathematical induction.
    explanationq132
Cancel reply
Cancel reply

30. The depth of a complete binary tree with 'n nodes is (log is to be base two)

  • Option : A
  • Explanation : If the depth is d, the number of nodes n will be 2 (d+1)-1
    So, n+1 = 2(d+1) or d = log (n+1)-1
Cancel reply
Cancel reply