Binary Trees: Structure, Operations, and Applications

Question 1

Which of the following statements about Binary Search Trees (BSTs) is incorrect?

Accepted Answer

All nodes in a BST have the same depth.

Answer

The left subtree of a node contains only keys less than the node's key.

Answer

The right subtree of a node contains only keys greater than or equal to the node's key.

Answer

The inorder traversal of a BST produces a sorted list of keys.

Question 2

In a binary search tree, the value of the left child is always:

Accepted Answer

Less than the parent node

Answer

Greater than the parent node

Answer

Equal to the parent node

Answer

Unrelated to the parent node

Question 3

The height of a complete binary tree with N nodes is:

Accepted Answer

Log(N) + 1

Answer

Log(N)

Answer

2 * Log(N)

Answer

N - 1

Question 4

Which of the following is NOT an application of binary trees?

Accepted Answer

Hash tables

Answer

File systems

Answer

Huffman coding

Answer

Binary search

Question 5

In a binary search tree, the inorder traversal will produce a list of nodes in:

Accepted Answer

Ascending order

Answer

Descending order

Answer

Random order

Answer

Unsorted order

Question 6

Which of the following is a balanced binary tree?

Accepted Answer

A tree with equal height subtrees for each node

Answer

A tree with all left children

Answer

A tree with all right children

Answer

A tree with a single node

Question 7

In an AVL tree, the balance factor of a node is the:

Accepted Answer

Difference between the heights of its left and right subtrees

Answer

Sum of the heights of its left and right subtrees

Answer

Product of the heights of its left and right subtrees

Answer

Height of the node

Question 8

Which of the following is NOT a property of a binary search tree (BST)?

Accepted Answer

The tree is always balanced in terms of height.

Answer

Each node's left child is less than or equal to the node.

Answer

Each node's right child is greater than the node.

Answer

Each node can have up to two children.

Question 9

What is the time complexity of searching for a key in a balanced binary search tree?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(1)

Question 10

In a binary tree traversal, which traversal technique visits the nodes in the following order: root, left subtree, right subtree?

Accepted Answer

Pre-order

Answer

In-order

Answer

Post-order

Answer

Level-order

Question 11

What is the primary purpose of an AVL tree?

Accepted Answer

Maintaining a balanced binary search tree

Answer

Storing key-value pairs efficiently

Answer

Performing efficient range queries

Answer

Representing hierarchical data

Question 12

What is the time complexity of inserting a node into an AVL tree?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(1)

Question 13

What is the distinction between a complete binary tree and a perfect binary tree?

Accepted Answer

A perfect binary tree is always complete, while a complete binary tree is not necessarily perfect.

Answer

A complete binary tree is always perfect, while a perfect binary tree is not necessarily complete.

Answer

They are identical types of binary trees.

Answer

There is no difference between the two.

Question 14

Which property ensures that all nodes in the left subtree of a binary search tree (BST) are less than the parent node?

Accepted Answer

Left child property

Answer

Inorder traversal

Answer

Balanced height

Answer

Right child property

Question 15

What is the time complexity of searching for an element in a balanced binary search tree with n nodes?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(log n^2)

Question 16

What is the maximum possible number of nodes in a full binary tree of height h?

Accepted Answer

2^h - 1

Answer

2^h - 2

Answer

2^h

Answer

h + 1

Question 17

Which of the following is not a property of AVL trees?

Accepted Answer

AVL trees are always perfectly balanced.

Answer

Every node has a balance factor of -1, 0, or 1.

Answer

The height of the left and right subtrees of any node can differ by at most 1.

Answer

AVL trees are a type of binary search tree.

Question 18

Which of the following is a fundamental property of a binary tree?

Accepted Answer

Each node has a maximum of two children.

Answer

All leaf nodes are at the same level.

Answer

The tree is inherently balanced.

Answer

The root node has the largest value.

Question 19

What is the time complexity of searching for a specific element in a binary search tree of height h?

Accepted Answer

O(log h)

Answer

O(h)

Answer

O(h^2)

Answer

O(1)

Question 20

What is the key difference between a full binary tree and a complete binary tree?

Accepted Answer

A full binary tree has all levels filled, while a complete binary tree has its last level partially filled.

Answer

A complete binary tree has all levels filled, while a full binary tree has its last level partially filled.

Answer

A full binary tree has every node with two children, while a complete binary tree has every node with at least one child.

Answer

There is no difference between a full binary tree and a complete binary tree.

Question 21

What is the maximum height of a binary tree with n nodes?

Accepted Answer

log2(n)

Answer

n

Answer

2n

Answer

n^2

Question 22

Which of the following is NOT an advantage of using binary trees over linear data structures?

Accepted Answer

Lower memory consumption

Answer

Efficient search operations

Answer

Simplified insertion and deletion

Answer

Improved data organization

Question 23

What is the primary role of a node in a binary tree?

Accepted Answer

To store data and maintain references to child nodes.

Answer

To represent a specific level within the tree.

Answer

To connect different subtrees.

Answer

To ensure the balance of the tree.

Question 24

Which of the following operations is NOT supported by a binary search tree?

Accepted Answer

Automatically rebalancing the tree after an operation

Answer

Inserting a new node

Answer

Deleting an existing node

Answer

Searching for a specific node

Question 25

What is a balanced binary tree?

Accepted Answer

A tree where the difference in height between the left and right subtrees of every node is at most one.

Answer

A tree where all leaf nodes are at the same level.

Answer

A tree where all internal nodes have two children.

Answer

A tree where the number of nodes in the left subtree is equal to the number of nodes in the right subtree.

Question 26

What is the average time complexity of searching for a key in a balanced binary search tree?

Accepted Answer

O(log n)

Answer

O(1)

Answer

O(n)

Answer

O(n^2)

Question 27

What condition must be met for a binary tree to qualify as a heap?

Accepted Answer

Every node's value is greater than or equal to its parent's value.

Answer

Every node's value is less than or equal to its parent's value.

Answer

The left child is always smaller than the right child.

Answer

The tree is perfectly balanced.

Question 28

What is the minimum number of nodes in a complete binary tree of height h?

Accepted Answer

2^(h+1) - 1

Answer

h

Answer

2^h

Answer

2^(h-1) + 1

Question 29

How do red-black trees differ from binary search trees?

Accepted Answer

Red-black trees maintain a more balanced structure.

Answer

Red-black trees allow for duplicate values.

Answer

Binary search trees are more efficient for searching.

Answer

There is no difference between them.

Question 30

Which of the following is a defining characteristic of a binary tree?

Accepted Answer

Each internal node has at most two child nodes.

Answer

The tree is ordered based on the values of its nodes.

Answer

The tree is always perfectly balanced.

Answer

The tree is used exclusively to represent hierarchical data.

Question 31

What is the primary difference between an inorder and preorder traversal of a binary tree?

Accepted Answer

Inorder traversal visits the left subtree before the root, while preorder traversal visits the root before the left subtree.

Answer

Inorder traversal visits the right subtree before the root, while preorder traversal visits the root before the right subtree.

Answer

Inorder traversal visits the nodes in ascending order, while preorder traversal visits the nodes in descending order.

Answer

Inorder traversal is used for searching, while preorder traversal is used for constructing the tree.

Question 32

Which of the following operations is not supported by a binary search tree (BST)?

Accepted Answer

Sorting the tree in ascending order

Answer

Inserting a new node

Answer

Deleting an existing node

Answer

Searching for a node with a given value

Question 33

What is the critical difference between a binary search tree (BST) and an AVL tree?

Accepted Answer

AVL trees are always balanced, while BSTs can become unbalanced.

Answer

BSTs allow duplicate values, while AVL trees do not.

Answer

BSTs are used for searching, while AVL trees are used for sorting.

Answer

AVL trees have a more straightforward insertion algorithm than BSTs.

Question 34

What is the height of a complete binary tree with n nodes?

Accepted Answer

log2(n)

Answer

2^n - 1

Answer

n

Answer

n - 1

Question 35

What is the best-case time complexity of searching for a node in a perfectly balanced binary tree?

Accepted Answer

O(log n)

Answer

O(1)

Answer

O(n)

Answer

O(n log n)

Question 36

What is the minimum number of nodes needed to create a full binary tree with a height of h?

Accepted Answer

2^(h + 1) - 1

Answer

2^h

Answer

h + 1

Answer

2^(h - 1)

Question 37

What is the time complexity of a successful search operation in a balanced binary search tree with n nodes?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(1)

Question 38

What is the purpose of the balance factor in an AVL tree?

Accepted Answer

To maintain balance between its left and right subtrees.

Answer

To track the number of insertions and deletions.

Answer

To store the number of nodes in the tree.

Answer

To indicate the depth of the tree.

Question 39

Which of the following traversal orders visits nodes in the sequence: root, left subtree, right subtree?

Accepted Answer

Preorder

Answer

Level-order

Answer

Inorder

Answer

Postorder

Question 40

Which of the following is a disadvantage of using binary trees instead of arrays?

Accepted Answer

Slower random access.

Answer

Better cache locality.

Answer

Greater memory efficiency.

Answer

Easier insertion and deletion.

Question 41

What is the maximum possible number of nodes in a complete binary tree of height h?

Accepted Answer

(2^h) - 1

Answer

2^h

Answer

2^(h+1)

Answer

2^(h-1)

Question 42

Which of the following operations can be performed on a binary tree?

Accepted Answer

Traversing, searching, and inserting

Answer

Only searching and balancing

Answer

Only deleting and rotating

Answer

Only traversing and inserting

Question 43

Which of the following techniques can be used to maintain the balance of an AVL tree?

Accepted Answer

Single rotation and double rotation

Answer

Only double rotation

Answer

Only single rotation

Answer

Neither single rotation nor double rotation

Question 44

What is the minimum possible height of an AVL tree with n nodes?

Accepted Answer

log(n) + 1

Answer

n - 1

Answer

n + 1

Answer

2^(n)

Question 45

What is the primary advantage of using a threaded binary tree?

Accepted Answer

Reduced space overhead by eliminating pointers

Answer

Easier insertion and deletion of nodes

Answer

Improved search efficiency

Answer

Guaranteed sorted order of elements

Question 46

In a binary search tree, how are values organized relative to a node's value?

Accepted Answer

Values in the left subtree are smaller, and values in the right subtree are larger than the node's value.

Answer

Values in both subtrees can be either smaller or larger than the node's value.

Answer

Values in the left subtree are larger, and values in the right subtree are smaller than the node's value.

Question 47

What is the primary advantage of using an AVL tree compared to a regular binary search tree?

Accepted Answer

AVL trees automatically maintain balance, ensuring efficient search operations even with skewed data insertions.

Answer

AVL trees provide faster insertion and deletion operations than regular binary search trees.

Answer

AVL trees are more memory-efficient than regular binary search trees.

Question 48

What is the maximum height of a complete binary tree with 'n' nodes?

Accepted Answer

log₂(n+1) - 1

Answer

n/2

Answer

n

Question 49

Which operation is NOT commonly associated with binary tree data structures?

Accepted Answer

Concatenation

Answer

Insertion

Answer

Deletion

Question 50

What is the time complexity of searching for a specific value in a balanced binary search tree?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n log n)

Answer

O(1)

Question 51

In a binary tree, how does the number of nodes relate to the number of edges?

Accepted Answer

There is always one fewer edge than nodes in a binary tree.

Answer

The number of edges is always twice the number of nodes.

Answer

The number of edges always equals the number of nodes.

Question 52

What is the purpose of calculating the 'balance factor' in an AVL tree?

Accepted Answer

To determine if a node is out of balance and requires a rotation to maintain the tree's balance.

Answer

To calculate the height of the tree for optimization purposes.

Answer

To identify the node with the highest value in the tree.

Question 53

Which algorithm is commonly employed to construct a binary search tree from an unsorted array?

Accepted Answer

In-order insertion

Answer

Merge sort

Answer

Quick sort

Answer

Heap sort