BST Practice — Properties, Traversals & Operations¶

Draw the resulting tree. Label every node with its ID.

1. What is the height of the tree?
2. What is the depth of node 60?
3. How many leaf nodes does the tree have?
4. How many internal nodes (non-leaves) does the tree have?
5. Is the tree balanced? Justify your answer in one sentence.

Write the output of each traversal:

1. In-Order (Left → Root → Right)
2. Pre-Order (Root → Left → Right)
3. Post-Order (Left → Right → Root)

Then answer: which traversal would you use to print all products sorted by ID? Why?

1. Delete 20 — identify the case first, then redraw.
2. Delete 70 — identify the case first, then redraw.
3. Delete 50 — identify the case first, then redraw.

For each deletion, state which case applies:

• Case 1 — Leaf (no children)
• Case 2 — One child
• Case 3 — Two children → identify the in-order successor before redrawing

Answer the following in 1–2 sentences each:

1. After all three deletions in Part D, is the tree still a valid BST? How would you verify this without code?
2. What would happen to the tree's efficiency if you had inserted the original values in sorted order (20, 30, 40, 50, 60, 70, 80) instead?
3. Name one real-world scenario where you would choose a BST over a sorted array. What property of a BST makes it the better fit?

1. Which field do you choose as the key and why?
2. What breaks if you pick price as the key? What breaks if you pick name?
3. What happens when a product's price changes after it has already been inserted?

Deliverable: A short written justification (5–7 sentences) + present your decision to the class. Be ready to defend it.

1. How does the BST handle an exact ID search? Trace the steps for search(75) on a small example tree.
2. Can a BST keyed on id efficiently return all products in a price range? Why or why not?
3. What data structure would you recommend for price-range queries instead?

Deliverable: A diagram showing the search path for an exact lookup + a written recommendation for the price-range feature with justification.

1. Draw what the BST looks like after inserting just the first 6 products from this file.
2. What is the worst-case search time for this tree? Express it in terms of $n$.
3. How would you fix the loading strategy — without changing the BST code itself — so the tree stays balanced?

Deliverable: Two tree diagrams (bad load vs. good load) + a one-paragraph explanation of your fix.

1. Trace delete(70) on the tree below. Which case applies? What is the in-order successor? text [50] / \ [30] [70] / \ / \ [20] [40] [60] [80]
2. A junior developer implements updatePrice(id, newPrice) as: delete the product, then re-insert it with the new price. What could go wrong?
3. Write pseudocode for a safer update() method that avoids this problem.

Deliverable: The redrawn tree after deletion + pseudocode for update() + a one-sentence risk warning.

1. At what point does a standard BST become a liability in this system? What is the specific risk?
2. What is a self-balancing BST and what problem does it solve? Name one example (AVL or Red-Black tree).
3. Research one real database or system that uses a tree structure internally. Why did they choose it?

Deliverable: A one-slide pitch — "We recommend switching to X because..." — presented to the class in 3 minutes.

Implement the following two methods in ProductBST.java:

public Product findMin() {
    // your code here
}

public Product findMax() {
    // your code here
}

Constraints: - Both methods must be iterative (no recursion). - If the tree is empty, return null. - Do not traverse the entire tree — use the BST property to go directly to the answer.

Verify your solution by calling both methods on the catalog from Main.java and confirming: - findMin() returns [ID: 25 | Mouse | $25.00] - findMax() returns [ID: 175 | Headphones | $150.00]

Implement the following method in ProductBST.java:

public int countLeaves() {
    // your code here
}

Constraints: - Must be recursive. - An empty tree has 0 leaves. - A tree with only a root node has 1 leaf.

Verify your solution on the catalog from Main.java: - The 7-node catalog should return 4 leaves: nodes 25, 75, 125, 175.

Then answer in a comment: what is the time complexity of countLeaves()? Why can it not do better than that?

Implement the following method in ProductBST.java:

public Product searchByName(String name) {
    // your code here
}

Constraints: - The search must be case-insensitive ("webcam" and "Webcam" both match). - Return the first matching product found, or null if no match exists. - You may not add any new fields or restructure the tree.

Then answer the following in a comment above the method: 1. What traversal strategy did you use and why? 2. What is the time complexity of this method compared to search(int id)? 3. Why is the BST property of no help here?

Implement the following method in ProductBST.java:

public boolean isSkewed() {
    // your code here
}

Constraints: - Return true if every node in the tree has at most one child. - An empty tree and a single-node tree both return true. - Must work for both left-skewed and right-skewed trees.

Verify your solution with two cases: - The balanced 7-node catalog from Main.java → should return false. - A tree built by inserting 10, 20, 30, 40 in that order → should return true.

Then answer in a comment: if isSkewed() returns true on your catalog, what does that tell you about the order products were inserted? What would you do to fix it?