Week 4 - Binary Search Tree (BST)

Question 1

What is Key Idea 1 behind using a Binary Search Tree (BST)?

Answer 1

A large balanced or nearly balanced tree has a small height, which helps keep operations like search, insert, and delete efficient — ideally O(log n) time.

Question 2

Why is keeping a small height important in BSTs?

Answer 2

A small height reduces the number of steps needed to traverse the tree, allowing for faster access to elements and better overall performance.

Question 3

What is Key Idea 2 behind Binary Search Trees?

Answer 3

BSTs are structured so that:

The left subtree contains values less than the parent.

The right subtree contains values greater than the parent.

This ordering allows for fast lookup using binary search logic.

Question 4

Can a Binary Search Tree contain duplicate values?

Answer 4

In the simplified version of BSTs, no duplicate values are allowed. Each value is unique and appears only once in the tree.

Question 5

What does In-order Traversal (LNR) stand for?

Answer 5

LNR stands for:

1. Left subtree
2. Node (current node)
3. Right subtree
   It processes the left, then current, then right recursively.

Question 6

What are the steps in In-order Traversal?

Answer 6

1. Recursively traverse the left subtree
2. Visit the current node
3. Recursively traverse the right subtree

Question 7

What is a common use case for In-order Traversal?

Answer 7

In-order traversal is used when you want to process or display a BST’s data in sorted (ascending) order.

Question 8

What is the result of In-order traversal on a binary search tree?

Answer 8

It produces a sorted sequence of values in ascending order, since BST properties ensure left < node < right.

Question 9

What does Post-order Traversal (LRN) stand for?

Answer 9

LRN stands for:

1. Left subtree
2. Right subtree
3. Node (current node)
   It processes all children before the parent

Question 10

What are the steps in Post-order Traversal?

Answer 10

1.Recursively traverse the left subtree

2. Recursively traverse the right subtree
3. Visit the current node

Question 11

What is a common use case for Post-order Traversal?

Answer 11

It is used when you need to process all descendants of a node before the node itself, such as

• Deleting/freeing memory in trees
• Evaluating expression trees (bottom-up)

Question 12

How is Post-order Traversal different from In-order?

Answer 12

Post-order: processes children first, then the node

In-order: processes left, then node, then right

Post-order is useful for bottom-up tasks, while in-order is used for sorted output (in BSTs).