CMPT 125 Study Guide - Final Guide: Maximal And Minimal Elements, Binary Tree

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 125
• Professor: Igor Shinkar

Document Summary

Review part 2 struct btnode { int data; // struct btnode* left; // left child struct btnode* right; // right child struct btnode* parent; typedef struct btnode btnode_t; typedef struct binary_tree { struct btnode* root; Write a function that gets a root of a bst and returns the minimal element in the tree. int findmin (btnode* root){ Suppose that for every node in the tree it holds that (node->left == null || node->left->data <= node->data) Create a binary search tree from the following list of insertions: List1: 7, 1, 3, 2, 4, 5, 6. List2: 1, 3, 2, 5, 4, 7, 6. List3: 5, 8, 3, 1, 4, 2, 6, 7, 9. Answer: for the first element (the root) we choose either min or max. Then, for the second element we choose either min or max of the remaining elements (2n). In the third step, again, we may choose either min or max of the remaining elements (2 n-1)