trees

Question 1

What is a graph?

Answer 1

A structure of nodes (vertices) connected by edges that model relationships.

Question 2

What are the components of a graph?

Answer 2

Vertices (nodes) and edges (connections between nodes).

Question 3

What is a directed graph?

Answer 3

A graph where edges have direction (arrows from one node to another).

Question 4

What is an undirected graph?

Answer 4

A graph where edges have no direction; connections are bidirectional.

Question 5

What is a weighted graph?

Answer 5

A graph where edges carry weights, often representing cost or distance.

Question 6

What is a path in a graph?

Answer 6

A sequence of connected edges where each edge leads to the next node.

Question 7

What is a cycle in a graph?

Answer 7

A path that starts and ends at the same node with all edges distinct.

Question 8

What does it mean for a graph to be connected?

Answer 8

There is a path between every pair of vertices.

Question 9

What is an acyclic graph?

Answer 9

A graph with no cycles.

Question 10

What defines a tree in graph theory?

Answer 10

An undirected, connected, and acyclic graph.

Question 11

How many paths are there between two nodes in a tree?

Answer 11

Exactly one path.

Question 12

What is a rooted tree?

Answer 12

A tree with one node designated as the root; defines levels in the tree.

Question 13

What is a level in a tree?

Answer 13

The number of edges from the root to a given node.

Question 14

What is the main difference between BFS and DFS?

Answer 14

BFS uses a queue (FIFO) to explore level-by-level; DFS uses a stack (LIFO) to go deep first.

Question 15

Why must you track visited nodes in graph traversal?

Answer 15

To avoid revisiting nodes and prevent infinite loops in cyclic graphs.

Question 16

Why don’t you need to track visited nodes in trees?

Answer 16

Because trees are acyclic and each node is reached only once.

Question 17

What is preorder traversal?

Answer 17

Visit root, then traverse left subtree, then right subtree.

Question 18

What is postorder traversal?

Answer 18

Traverse left subtree, then right subtree, then visit root.

Question 19

What is inorder traversal?

Answer 19

Traverse left subtree, visit root, then traverse right subtree (binary trees only).

Question 20

What is level-order traversal?

Answer 20

Traverse nodes level by level using a queue — same as BFS.

Question 21

Which traversal method uses a queue?

Answer 21

Breadth-first search (BFS) and level-order traversal.

Question 22

Which traversal method uses a stack or recursion?

Answer 22

Depth-first search (DFS), preorder, postorder, and inorder traversals.

Question 23

Why might a hash table not be suitable for range queries?

Answer 23

Because hash tables do not maintain any ordering of keys.

Question 24

What kind of data structure allows efficient key-based lookup and range queries?

Answer 24

A binary search tree (BST).

Question 25

What property defines a binary search tree (BST)?

Answer 25

For each node, all keys in the left subtree are smaller, and all keys in the right subtree are larger.

Question 26

What traversal of a BST gives keys in sorted order?

Answer 26

Inorder traversal.

Question 27

What is the average-case time complexity of search in a BST?

Answer 27

O(log n) if the tree is balanced.

Question 28

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

Answer 28

O(n), if the tree is skewed.

Question 29

What causes poor performance in an unbalanced BST?

Answer 29

Insertion of keys in sorted order, creating a degenerate (linear) tree.

Question 30

What is the expected height of a random BST?

Answer 30

O(log n), as shown in a 2003 paper by Bruce Reed.

Question 31

What is the motivation for AVL trees?

Answer 31

To maintain balance and guarantee O(log n) operations even in the worst case.

Question 32

What does AVL stand for?

Answer 32

Adelson-Velsky and Landis — the inventors of AVL trees.

Question 33

What is the balance factor of a node in an AVL tree?

Answer 33

The height of the right subtree minus the height of the left subtree.

Question 34

What balance factors are allowed in an AVL tree?

Answer 34

-1, 0, or 1.

Question 35

What happens when the balance factor goes outside the allowed range?

Answer 35

A rotation (single or double) is performed to restore balance.

Question 36

What is a single rotation in AVL trees?

Answer 36

A restructure where a child node replaces its parent to reduce imbalance (used in LL or RR cases).

Question 37

What is a double rotation in AVL trees?

Answer 37

Two successive rotations used for LR or RL imbalances to restore balance.

Question 38

What is preserved after rotations in AVL trees?

Answer 38

The binary search tree property and the inorder traversal order.

Question 39

What is the time complexity of insert/delete in an AVL tree?

Answer 39

O(log n), due to rebalancing.

Question 40

How is balance restored after insertion or deletion in AVL trees?

Answer 40

By updating balance factors and performing rotations if necessary.

Question 41

What additional information is stored in AVL tree nodes?

Answer 41

Height and balance factor.

Question 42

What is the main advantage of an AVL tree over a regular BST?

Answer 42

AVL trees guarantee balanced height, ensuring efficient operations.