Chapter 19: Problem 14

Give an algorithm for a function int smallest (TreeNode *tree) that takes a pointer to a root of a binary search tree as parameter and returns the smallest value stored in the tree.

Short Answer

Expert verified

Answer: The 'smallest' function is used to find and return the smallest value stored in a binary search tree. It does this by traversing through the left subtree of the tree, since the left subtree contains values less than the root, until it reaches a leaf node.

Step by step solution

Function Declaration and Base Case

Declare the function 'int smallest(TreeNode *tree)' and check for the base case. If the tree is null, there is no smallest value, so return INT_MAX (the maximum value an int can hold). ```cpp #include int smallest(TreeNode *tree) { if (tree == nullptr) { return INT_MAX; } ```

Traverse Left Subtree

Traverse the left subtree by calling the 'smallest' function recursively, until reaching a leaf node. ```cpp int left_smallest = smallest(tree->left); ```

Compare Node Values

Compare the current node's value with the smallest value found in the left subtree. Return the smaller value. ```cpp return min(tree->value, left_smallest); } ``` Now that the algorithm is complete, here's the final code: ```cpp #include int smallest(TreeNode *tree) { if (tree == nullptr) { return INT_MAX; } int left_smallest = smallest(tree->left); return min(tree->value, left_smallest); } ```

Unlock Step-by-Step Solutions & Ace Your Exams!

Full Textbook Solutions
Get detailed explanations and key concepts
Unlimited Al creation
Al flashcards, explanations, exams and more...
Ads-free access
To over 500 millions flashcards
Money-back guarantee
We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

Recommended explanations on Computer Science Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Give an algorithm for a function int smallest (TreeNode *tree) that takes a pointer to a root of a binary search tree as parameter and returns the smallest value stored in the tree.

Short Answer

Step by step solution

Function Declaration and Base Case

Traverse Left Subtree

Compare Node Values

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Problem Solving Techniques

Data Structures

Algorithms in Computer Science

Functional Programming

Computer Network

Theory of Computation

Study anywhere. Anytime. Across all devices.