[go: up one dir, main page]
Scribd
Upload
7 views4 pages

tree_theroy_question

Tree thery

Uploaded by

nikhilagarwal284
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
7 views4 pages

tree_theroy_question

Tree thery

Uploaded by

nikhilagarwal284
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Tree Questions

1. Which traversal technique visits nodes in the order: left, root, right?

A) Preorder
B) Inorder
C) Postorder
D) Level order

Answer: B) Inorder
Explanation: Inorder traversal in a binary tree involves visiting the left subtree, then the root, and
finally the right subtree.

2. Which of the following data structures is used in implementing a binary tree level-order
traversal?

A) Stack
B) Queue
C) Array
D) Linked list

Answer: B) Queue
Explanation: Level-order traversal uses a queue to visit nodes level by level.

3. Which property of a Binary Search Tree (BST) allows efficient searching?

A) Elements in random order


B) Smaller elements on the left, larger on the right
C) Depth of the tree
D) Balanced structure

Answer: B) Smaller elements on the left, larger on the right


Explanation: The BST property enables efficient binary search, as elements are ordered based on
value.

4. What is the height of an AVL tree with n nodes in the worst case?

A) O(log n)
B) O(n)
C) O(nlog n)
D) O(n2)

Answer: A) O(log n)
Explanation: AVL trees are balanced, so the height is logarithmic, ensuring efficient operations.

5. Which rotation is performed when an AVL tree has an imbalance with a left-left case?

A) Left rotation
B) Right rotation
C) Left-right rotation
D) Right-left rotation
Answer: B) Right rotation
Explanation: A left-left imbalance is corrected by a single right rotation.

6. In a binary tree, which traversal visits nodes in root, left, right order?

A) Inorder
B) Preorder
C) Postorder
D) Level order

Answer: B) Preorder
Explanation: Preorder traversal visits the root first, followed by the left and right subtrees.

7. In an AVL tree, what is the maximum difference allowed between the heights of left and right
subtrees?

A) 0
B) 1
C) 2
D) No limit

Answer: B) 1
Explanation: The balance factor of any node in an AVL tree should not exceed 1 to maintain balance.

8. In a binary tree, which traversal technique can be implemented without recursion or stack?

A) Preorder
B) Inorder
C) Postorder
D) Level order

Answer: D) Level order


Explanation: Level-order traversal uses a queue, which doesn’t require recursion or a stack.

9. What is the maximum number of nodes in a binary tree of height h?

A) 2h−1
B) 2h+1−1
C) 2h−1
D) 2h−1−1

Answer: B) 2h+1−1
Explanation: A full binary tree of height h has 2h+1−1 nodes.

10. Which of the following statements is true about AVL trees?

A) They are balanced with a height difference of 2.


B) They are balanced with a height difference of at most 1.
C) They have the smallest height among all trees.
D) All levels are filled except possibly the last.

Answer: B) They are balanced with a height difference of at most 1.


Explanation: The balance factor in AVL trees is limited to ±1 for efficient performance.

11. In an AVL tree, if inserting a node causes a left-left imbalance, which rotation will correct this?
A) Left rotation
B) Right rotation
C) Left-right rotation
D) Right-left rotation

Answer: B) Right rotation


Explanation: A left-left imbalance requires a single right rotation to restore balance.

12. In a binary tree, how many edges are there if the tree has n nodes?

A) n−1
B) n
C) n+1
D) 2n

Answer: A) n−1
Explanation: A binary tree with n nodes has n-1 edges.

13. If a node with one child is deleted from a BST, what happens to the child node?

A) It is deleted as well
B) It replaces the deleted node
C) It becomes a new root node
D) No change occurs

Answer: B) It replaces the deleted node


Explanation: When deleting a node with one child, the child node takes the deleted node’s place.

14. If a BST is built by inserting the elements 30, 10, 20, 40, 50, what would be the in-order
traversal of the BST?

A) 30 10 20 40 50
B) 10 20 30 40 50
C) 50 40 30 20 10
D) 10 30 20 40 50

Answer: B) 10 20 30 40 50
Explanation: In-order traversal of a BST lists elements in sorted ascending order.

15. Which of the following statements is true about AVL trees compared to BSTs?

A) AVL trees allow faster insertion than BSTs


B) AVL trees have shorter heights than BSTs
C) BSTs are always balanced
D) BSTs require more memory than AVL trees

Answer: B) AVL trees have shorter heights than BSTs


Explanation: AVL trees are height-balanced, so they often have a shorter height than unbalanced
BSTs, providing faster search.

16. What is the height of a binary tree?

A) The number of nodes in the tree.


B) The number of edges on the longest path from the root to a leaf.
C) The number of leaf nodes in the tree.
D) The number of internal nodes in the tree.

Answer: B) The number of edges on the longest path from the root to a leaf
Explanation: Option B is correct. The height of a binary tree is the number of edges on the longest
path from the root to a leaf.

17. In an expression tree, what does a leaf node represent?

A) An operator
B) An operand
C) A function
D) A variable

Answer: B) An operand
Explanation: Option B is correct. In an expression tree, a leaf node represents an operand, which can
be a constant or a variable.

You might also like