Data Structures Trees and Binary Search Trees

Question 1

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

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(√n)

Answer

O(n log n)

Question 2

Which tree traversal visits nodes in ascending order for a Binary Search Tree?

Accepted Answer

In-order

Answer

Pre-order

Answer

Post-order

Answer

Level-order

Question 3

What property must a Binary Search Tree satisfy at every node?

Accepted Answer

All left descendants < node value < all right descendants

Answer

Left child equals parent value

Answer

Left subtree height equals right subtree height

Answer

Node value is greater than all nodes in the tree

Question 4

What is the worst-case time complexity of search in an unbalanced BST?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n log n)

Question 5

Which self-balancing BST uses red-black coloring to maintain O(log n) operations?

Accepted Answer

Red-Black tree

Answer

AVL tree

Answer

B-tree

Answer

Splay tree

Question 6

What is the lowest common ancestor (LCA) of two nodes in a BST?

Accepted Answer

The deepest node that is an ancestor of both nodes

Answer

The root of the tree

Answer

The parent of the shallower node

Answer

The node with value equal to the average of both nodes