7.1 Search, Insertion, Deletion and Sorting

Basic Skills

1. Given the binary tree below, which node is the root?

2. In a BST, where would the value 5 be inserted if the current tree contains the values 2, 4, 6, and 8?
3. Which of the following nodes is a leaf in the tree below?

4. What happens when a node with two children is deleted from a binary search tree?
5. Which tree traversal method is typically used to retrieve values from a binary search tree in sorted (ascending) order?

Applications

6. A binary search tree contains the values 5, 3, 8, 2, 4, 7, and 9. Describe the steps the algorithm would take to search for the value 7. How many comparisons are needed?
7. A company maintains a binary search tree to store employee IDs. The current tree contains 1001, 1005, and 1010. An employee with ID 1003 joins the company. Where will this ID be inserted in the tree, and why?
8. In a binary search tree, what steps are taken when deleting a node with two children? Illustrate your answer with an example using the tree:

9. A web application stores user ratings in a binary search tree. To display the ratings in ascending order, which traversal method should be used? Explain why this method works.
10. A file system uses a tree structure to organize folders and files. Explain how insertion and deletion operations in this tree model correspond to creating and removing folders or files in an operating system.

Challenge Problems

11. Given the in-order traversal D, B, E, A, F, C and the pre-order traversal A, B, D, E, C, F of a binary tree, reconstruct the original tree structure.
12. Analyze the worst-case time complexity of deleting a node from a binary search tree. Under what conditions does this worst-case scenario occur, and how can it be mitigated?
13. Compare the performance of search operations in a balanced binary search tree versus an unbalanced tree. Provide an example where the performance difference is significant.
14. Explain how a binary search tree can be used to sort a list of numbers. Then, describe a scenario where this method performs poorly and suggest an alternative tree-based sorting approach.
15. A decision tree is used to classify whether a transaction is fraudulent based on three binary features: is_large_amount, is_foreign_location, and is_new_account. Design a simple decision tree structure and explain how it would classify the transaction (True, False, True).

7.2 Complexity

Basic Skills

16. What is the time complexity of searching for a value in a balanced binary search tree?
17. In an unbalanced binary search tree, what is the worst-case time complexity for searching a value?
18. How does the height of a binary tree affect the performance of search operations?
19. What is the average-case time complexity of inserting a node into a binary search tree?
20. Which data structure generally provides better worst-case performance for search operations: a balanced binary search tree or a linked list? Explain briefly.

Applications

21. A search engine uses a binary search tree to store indexed keywords. Explain how the tree’s balance affects the speed of keyword lookup, and what happens if the tree becomes unbalanced.
22. A developer needs to choose between using a binary search tree and a hash table for storing user IDs. Discuss the trade-offs in complexity for search, insertion, and deletion operations in both structures.
23. In a real-time embedded system, fast response time is critical. Why might a balanced tree be preferred over an unbalanced one for managing sensor data?
24. A database system uses a binary search tree to manage customer records. As the number of records grows, how does the tree’s height affect the time complexity of search operations?
25. A sorting algorithm uses a binary search tree to sort a list of 1,000 integers. Estimate the time complexity of the sorting process and explain how the tree structure influences performance.

Challenge Problems

26. Prove that the worst-case time complexity of searching in a binary search tree is [latex]O(n)[/latex]. Then, construct an example of a tree where this worst case occurs and explain why.
27. A binary search tree contains 1,000 nodes. Compare the maximum number of comparisons required to find a value in a balanced tree versus an unbalanced tree. Show your calculations and explain the performance implications.
28. A developer notices that search operations in their tree-based data structure are slowing down over time. What tree properties should they investigate, and what strategies could they use to restore optimal complexity?
29. An AVL tree is a type of self-balancing search tree named after its inventors Adelson-Velsky and Landis. It maintains its balance by ensuring that the height difference (also called the balance factor) between the left and right subtrees of any node is at most 1. Compare the time complexity of search, insertion, and deletion operations in a standard binary search tree versus an AVL tree. Under what conditions is the AVL tree more efficient?
30. A decision tree used for classification has a depth of 10. What is the worst-case time complexity for classifying a single input? How does pruning the tree affect this complexity?

7.3 Decision Trees

Basic Skills

31. What is a decision tree, and what does each internal node typically represent?
32. In a decision tree, what does a leaf node represent?
33. How many possible outcomes can a binary decision tree with 3 levels (excluding the root) have?
34. Consider a decision tree with conditions:

• • Is the user logged in?
  • Is the user an admin?
  • Is the request secure?

What is the decision path for a user who is logged in, not an admin, and the request is secure?

35. What is the purpose of traversing a decision tree from root to leaf?

Applications

36. A retail website uses a decision tree to determine if a customer qualifies for free shipping. The conditions are:

• • Order total [latex]\geq $50[/latex]
  • Customer is a member
  • Shipping address is domestic

Design a decision path that leads to free shipping and explain how the tree structure supports this logic.

37. A spam filter uses a decision tree with the following conditions:

• • Contains suspicious keywords
  • Sender is unknown
  • Message has attachments

Describe how the decision tree would classify a message that meets all three conditions.

38. An access control system uses a decision tree to determine whether to grant access. The conditions are:

• • User is authenticated
  • User has admin privileges
  • Access request is during business hours

Construct a decision path that results in access being denied and explain the reasoning.

39. In a machine learning model, a decision tree is used to predict customer churn. The features include:

• • Number of support tickets
  • Subscription length
  • Last login date

Explain how the decision tree might use these features to classify a customer as “likely to churn.”

40. A software troubleshooting tool uses a decision tree to guide users through diagnosing a system error. The conditions include:

• • Error message displayed
  • System logs available
  • Recent updates installed

Describe how the decision tree helps narrow down the cause of the error.

Challenge Problems

41. A decision tree used for loan approval has grown too deep, causing slow performance and overfitting. Propose a strategy to simplify the tree while preserving classification accuracy. What trade-offs might occur?
42. A decision tree classifies network traffic as safe or suspicious based on five binary features. How many distinct classification paths are possible? What challenges arise when interpreting such a tree?
43. Compare the use of a decision tree and a rule-based system for diagnosing hardware failures. Under what conditions would a decision tree be more efficient or interpretable?
44. Given the following dataset of user behaviour, construct a decision tree that predicts whether a user will click on an ad:

• • Time on site
  • Device type
  • Previous purchases

What criteria would you use to split the nodes, and how would you evaluate the tree’s accuracy?

45. In a decision tree used for medical diagnosis, some patient records have missing values. Describe two methods for handling missing data during tree construction and explain how each affects the tree’s reliability.