# Data Structure Questions and Answers – Binary Tree Properties

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on **Binary Tree Properties**.

**1. Construct a binary tree by using postorder and inorder sequences given below.Inorder: N, M, P, O, QPostorder: N, P, Q, O, M **

A)

B)

C)

**D)**

**Explanation: Here,Postorder Traversal: N, P, Q, O, MInorder Traversal: N, M, P, O, Q**The root node of the tree is the last visiting node in Postorder traversal. Thus, Root Node = ‘M’.

The partial tree constructed is:

The second last node in postorder traversal is O. Thus, node P becomes the left child of node O, and node Q becomes the right child of node Q. Thus, the final tree is:

**2. Construct a binary search tree by using postorder sequence given below.Postorder: 2, 4, 3, 7, 9, 8, 5.**

A)

**B) **

C)

D)

**Explanation:** Postorder sequence is 2, 4, 3, 7, 9, 8, 5.

In order sequence is the ascending order of nodes in the Binary search tree. Thus, the Inorder sequence is 2, 3, 4, 5, 7, 8, 9. The tree constructed using Postorder and Inorder sequence is

**3. Construct a binary tree using inorder and level order traversal given below.Inorder Traversal: 3, 4, 2, 1, 5, 8, 9Level Order Traversal: 1, 4, 5, 9, 8, 2, 3**

**A) **

B)

C)

D)

Explanation: Inorder Traversal: 3, 4, 2, 1, 5, 8, 9

Level Order Traversal: 1, 4, 5, 9, 8, 2, 3

In level order traversal the first node is the root node of the binary tree.

Thus the partially formed tree is:

In level order traversal, the second node is 4. Then, node 3 becomes the left child of node 4, and node 2 becomes the right child of node 4. The third node of level order traversal is 8. Then, node 5 becomes the left child of node 8, and node 9 becomes a right child of node 8. Thus, the final tree is:

4. Which of the following is not an advantage of trees?

A) Hierarchical structure

B) Faster search

C) Router algorithms**D) Undo/Redo operations in a notepad****Explanation: **Stack is used to performing undo/redo operations in a notepad. Trees have advantages such as hierarchical structure, faster search, and router algorithms.

**5. In a full binary tree if number of internal nodes is I, then number of leaves L are?**

A) L = 2*I**B) L = I + 1**

C) L = I – 1

D) L = 2*I – 1**Explanation:** The number of Leaf nodes in a full binary tree is equal to 1 + the Number of Internal Nodes i.e L = I + 1

**6. In a full binary tree if number of internal nodes is I, then number of nodes N are?**

A) N = 2*I

B) N = I + 1

C) N = I – 1**D) N = 2*I + 1****Explanation:** Relation between number of internal nodes(I) and nodes(N) is N = 2*I+1.

**7. In a full binary tree if there are L leaves, then total number of nodes N are?**

A) N = 2*L

B) N = L + 1

C) N = L – 1**D) N = 2*L – 1****Explanation: **The relation between a** **number of nodes(N) and leaves(L) is N=2*L-1.

**8. Which of the following is incorrect with respect to binary trees?**

A) Let T be a binary tree. For every k ≥ 0, there are no more than 2k nodes in level k

B) Let T be a binary tree with λ levels. Then T has no more than 2^{λ – 1} nodes

C) Let T be a binary tree with N nodes. Then the number of levels is at least ceil(log (N + 1))**D) Let T be a binary tree with N nodes. Then the number of levels is at least floor(log (N + 1))**

Explanation: In a binary tree, there are atmost 2k nodes in level k and 2^{k-1} total number of nodes. Number of levels is at least ceil(log(N+1)).

**9. What is a full binary tree?****A) Each node has exactly zero or two children**

B) Each node has exactly two children

C) All the leaves are at the same level

D) Each node has exactly one or two children

Explanation: A complete binary tree is one with exactly 0 or 2 children for each node.

**10. What is a complete binary tree?**

A) Each node has exactly zero or two children

B) A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from right to left**C) A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right**

D) A tree In which all nodes have degree 2

Explanation: A full binary tree is one that is fully filled, with the possible exception of the bottom level, which is filled from left to right. A complete binary tree is one in which each node has exactly zero or two children. A perfect binary tree is one in which each node, except leaf nodes, has a degree of two.

**11. What is the average case time complexity for finding the height of the binary tree?**

A) h = O(loglogn)

B) h = O(nlogn)

C) h = O(n)**D) h = O(log n)****Explanation:** We don’t have to traverse all of the nodes since they’re either part of the left sub tree or the right subtree, so the uncertainty is less than n. In the average case, assuming the nodes are distributed equally, the time complexity becomes O. (logn).

**12. The number of edges from the root to the node is called __________ of the tree.**

A) Height**B) Depth**

C) Length

D) Width

Explanation: The depth of the tree is defined as the number of edges from the root to the node.

**13. The number of edges from the node to the deepest leaf is called _________ of the tree.****A) Height**

B) Depth

C) Length

D) Width

Explanation: The height of the tree is defined as the number of edges from the node to the deepest leaf.

A binary tree is a non-linear data structure of the tree form with a maximum of two children per parent. Along with the data element, every node in a binary tree has a left and right relation. The root node is the node at the very top of a tree’s hierarchy.

The parent nodes are the nodes that contain other sub-nodes. The Binary Search Tree data structure is a node-based binary tree with the following properties.

Only nodes with keys lower than the node’s key are found in the left subtree of a node. Only nodes with keys greater than the node’s key are found in the right subtree of a node.