Trees - Practice MCQs for CCAT

Correct Answer: B - 2^k

At level k (0-indexed), max nodes = 2^k. Level 0 has 1, level 1 has 2, etc.

Correct Answer: A - n+1

A binary tree with n nodes has n+1 NULL pointers.

Correct Answer: D - log n

Height of complete binary tree is O(log n).

Correct Answer: A - Sorted order

Inorder traversal of BST gives elements in sorted (ascending) order.

Correct Answer: C - O(log n) average

BST search is O(log n) on average, O(n) worst case (skewed tree).

Correct Answer: B - Self-balancing BST

AVL tree is a self-balancing BST where height difference of subtrees ≤ 1.

Correct Answer: C - Queue

Level order (BFS) traversal uses queue.

Correct Answer: C - No parent

Root is the topmost node with no parent.

Correct Answer: D - n-1

A tree with n nodes always has exactly n-1 edges.

Correct Answer: C - Every node has 0 or 2 children

In full binary tree, every node has either 0 or 2 children.

Correct Answer: C - All levels filled except possibly last, filled left to right

Complete binary tree has all levels filled except possibly the last, which is filled from left to right.

Correct Answer: B - All internal nodes have 2 children and all leaves at same level

Perfect binary tree has all internal nodes with 2 children and all leaves at the same level.

Correct Answer: D - Root, Left, Right

Preorder: Root first, then Left subtree, then Right subtree (Root-Left-Right).

Correct Answer: B - Left, Right, Root

Postorder: Left subtree first, then Right subtree, then Root (Left-Right-Root).

Correct Answer: B - floor(log₂(n))

Minimum height is achieved in complete binary tree: floor(log₂(n)).

Correct Answer: C - O(log n) worst case operations

Red-Black tree is self-balancing, guaranteeing O(log n) for search, insert, delete.

Correct Answer: D - Database indexing and file systems

B-trees are optimized for disk access and widely used in databases and file systems.

Correct Answer: C - Deepest node that is ancestor of both

LCA is the deepest (lowest) node that has both given nodes as descendants.

Correct Answer: C - Priority Queue

Binary heap efficiently implements priority queue with O(log n) insert and extract.

Correct Answer: A - Inorder predecessor/successor

Threaded binary tree uses NULL pointers to store inorder predecessor or successor for efficient traversal.

Correct Answer: B - 2^(h+1) - 1

A binary tree of height h can have at most 2^(h+1) - 1 nodes, achieved when every level is completely filled (perfect binary tree).

Correct Answer: B - Inorder

Inorder traversal of a BST visits left subtree, root, then right subtree, which produces elements in ascending sorted order.

Correct Answer: B - O(log n)

In a balanced BST, the height is O(log n), so searching takes O(log n) time as we traverse from root to leaf at most.

Correct Answer: A - Randomorder

Randomorder is not a standard tree traversal method. The three standard depth-first traversals are Inorder, Preorder, and Postorder.

Correct Answer: A - Greater than or equal to its children

In a max-heap, the value of each node is greater than or equal to the values of its children, ensuring the maximum element is at the root.

Correct Answer: A - 7

The minimum number of nodes in an AVL tree of height h follows N(h) = N(h-1) + N(h-2) + 1. N(0)=1, N(1)=2, N(2)=4, N(3)=7.

Correct Answer: D - Left-Right double rotation

The LR case requires a Left-Right double rotation: first a left rotation on the left child, then a right rotation on the unbalanced node.

Correct Answer: B - Root, Left, Right

Preorder traversal visits the Root first, then recursively visits the Left subtree, followed by the Right subtree.

Correct Answer: A - ⌈n/2⌉

A complete binary tree with n nodes has ⌈n/2⌉ leaf nodes. This is because internal nodes occupy positions 1 to ⌊n/2⌋.

Correct Answer: C - O(n)

In the worst case, a BST can degenerate into a linked list (skewed tree), making the insertion time complexity O(n).

Correct Answer: D - Heap

A heap (min-heap or max-heap) is the most efficient data structure for implementing a priority queue, providing O(log n) insertion and extraction.

Correct Answer: B - Its inorder successor or predecessor

When deleting a node with two children in a BST, it is replaced by its inorder successor (smallest in right subtree) or inorder predecessor (largest in left subtree).

Correct Answer: B - ⌊log₂(n)⌋

The height of a complete binary tree with n nodes is ⌊log₂(n)⌋, as the tree is filled level by level.

Correct Answer: D - Every node has 0 or 2 children

A full (or strictly) binary tree is one where every node has either 0 or 2 children. No node has exactly one child.

Correct Answer: D - Height of left subtree - height of right subtree

The balance factor of a node in an AVL tree is defined as the height of its left subtree minus the height of its right subtree. It must be -1, 0, or 1.

Correct Answer: D - Queue

Level order (BFS) traversal uses a queue. Nodes are enqueued level by level and dequeued in FIFO order for processing.

Correct Answer: D - 30

With 3 distinct nodes, the number of distinct binary trees = Catalan(3) × 3! = 5 × 6 = 30. Catalan number gives structurally unique trees, multiplied by permutations of labels.

Correct Answer: A - At one of the leaf nodes

In a min-heap, the maximum element is always at one of the leaf nodes since every parent is smaller than its children.

Correct Answer: C - Left, Right, Root

Postorder traversal visits the Left subtree first, then the Right subtree, and finally the Root node.

Correct Answer: A - O(n)

Building a heap using the bottom-up (heapify) approach takes O(n) time, which is more efficient than inserting elements one by one (O(n log n)).

Correct Answer: D - AVL tree

An AVL tree is a self-balancing BST where the balance factor of every node is maintained between -1 and 1 through rotations.

Correct Answer: B - 9

For any binary tree, the number of nodes with 2 children = number of leaf nodes - 1. So it has 10 - 1 = 9 such nodes.

Correct Answer: A - The rightmost node in its left subtree

The inorder predecessor of a node in a BST is the rightmost (maximum) node in its left subtree.

Correct Answer: A - O(n)

The space complexity is O(n) in the worst case (skewed tree) due to the recursion stack. For a balanced tree, it is O(log n).

Correct Answer: A - Array

A binary heap is typically implemented using an array where for a node at index i, its children are at 2i+1 and 2i+2, making it space-efficient.

Correct Answer: C - Inserting an element

Inserting an element into a max-heap takes O(log n) time as the element may need to be bubbled up from leaf to root. Finding max is O(1) since it's at the root.

Correct Answer: B - n - 1

A tree with n nodes always has exactly n - 1 edges. This is a fundamental property of trees.

Correct Answer: A - A right-skewed tree

Inserting sorted keys {1, 2, 3, 4, 5} into a BST produces a right-skewed tree where each node has only a right child.

Correct Answer: D - Preorder

Preorder traversal is used to create a copy of a binary tree because it processes the root before its subtrees, allowing proper tree construction.

Correct Answer: C - 2

After an insertion in an AVL tree, at most 2 rotations (a double rotation) are needed to restore balance at the first unbalanced ancestor.