Tree Data Structures
Binary Tree Notes!!
So far, to make a tree structure, you would need to modify the Node Traversal( a node would point to multiple different pointers.
The Visual of the tree structure:
reminds me of parent class and child class from object-oriented Java. With this, it is non-linear, since it is pointing to multiple nodes at once, not like a queue with a back and front since that is linear.
Binary Tree Structure: at MOST 2 children pointers possible // only for this course
It has a root, which is the first node.
With parent and child node, it’s set up based on which ones it is directly connected to,
With leaf nodes, that is one with no children, they point to NULL
With ones on the same plane/level, it could be considered siblings. // for this class, really only parent child, but there are different “family” terms that can represent the nodes
A subtree is a non-root node, a subsection of the whole tree, represents a smaller subset of the original tree
There are multiple levels of a tree, so that the same level can be from the same height(ones on the same plane as other ones)
With counting, from L0, L1, L2, L3, for example, the height would be 3, it doesn’t count the ground floor/root node as a level. // highest level == height of tree
With a degree, just from one node, how many children it is pointing to.
The depth is the longest path from a root node to a leaf node, with previous example, it is three,
With Height, it can be determined through , with n being number of nodes in the tree, but take integer division of that term(different from determining runtime of logn algorithms)
Complete Binary Tree: Every level, except the last, is completely filled, and all nodes are as far left as possible, essentially, think L0 =1, L1 = 2, L2 = 4, L3, 8
Example of Complete Binary tree:
Note: with an array, it would be in this order, reading from left to right in each position, like shown above, (memorize the pattern like a Karnaugh map)
A full Binary Tree is when each level has something that points to two children
Example of Full Binary Tree:
Comparing Complete/Full Binary Trees
Back to Height, how to determine the Max number of nodes from the height/max level
maxNodes = // h is the height, makes sense since this is binary
height = ceil
if we have 15 nodes, it will be log(16) which is 4, minus one, which is 4 - 1 = 3; Rounding up via ceil/ using integer divison to round down is fine. (Second one I think so)
ceil: ceiling function from Intro to C, it rounds up a decimal result
Binary Tree Linked List Implementation!
How To Traverse through a tree:
A depth-first search explorers a path all the way to a leaf before backtracing and exploring another path, nodes are explored in this order:
A B D E H L M N I O P C F G J K Q
This was a trinary tree, that’s why i was confused, it doesn’t count as a binary tree.
Okay, you would start with
traverse(root){ // inputing a root
traverse(root->left); // it sends to the left side
traverse(root->right); // and to the right side
}
Three ways to traversing a binary tree.
Preorder: the root is visited before its left and right subtrees
Inorder: the root is visited between the subtrees.
Postorder: the root is visited after both subtrees.
Preorder with examples
Examples:
Inorder with examples
Postorder and examples
/
final thoughts on the depth-first searches
I understand how the three work, with the first one, it will read root first, then left, right.
The second with do left, then root, then right.
The third will do left, then right, then finally the root.
The lines of recursion is honestly pretty simple code wise, but i have to grasp it more conceptually how it works. Simple ≠ easy.
Binary Search Tree
With a binary search tree, the left child’s value & subtree are smaller than the current node, while the right child’s value & their subtree are larger than the current node.
Okay, this example tree isn’t a complete tree(since not every child except last level is full), nor a full tree(since it needs to be either 0 or two children, and node 14 breaks that, since it has one child)
okay, with it
// when target is smaller, move to left side
// when target is larger, move to right side
// when target == the node, found it.
//Worst case scenario, if there is only one side in sorted order, it is O(n)
// otherwise, the best/average case is O(log(n)) time. Binary Trees: Search & Insert
(search is more important than insert/delete, since you need to find the node before them. )
With duplicate terms, the values aren’t consecutive, since with the example one before, it would insert the second 6 node on the right child of 4.
Searching/Inserting
Have to create the node we want to insert first.
Create Node
How To insert
Example, so far, with this list
10,14,6,2,5,15,17
with 10, it would be the parent node/ root of the tree
with 14, it would be inserted in the right subtree, nothing is there, so it would replace the right child with the pointer of 14.
then it keeps going, with 6 being the left subchild of 10, then 2 being the left subchild of 6, and 5 being the right subchild of 2.
Then it goes for 15 and 17 being the right subtree of 14, and 15, respectively.
for instance with 57, it will traverse from 43, 64, 56, 59, and end being the left child of 57.
Main for this:
Keep asking for values, it will make a temp_node with that value, and add to my_root, by inserting the root, and the temp_node, increasing the tree.
Recursion Version/Insert Implementation for Binary search tree
okay, with this, the if statement determines if it goes into the right subtree, then checking if there something there(and if there is, since it isn’t NULL), then it calls it again for root→right, else you would place the element there.
The else statement checks for the left side(if not right, then it is left)
doing the same thing, but int terms of left, checking if there is something there(not NULL) and if there is, traverses through root→left, otherwise, insert that element there.
At the end, it returns the root pointer of the updated tree, so the tree is now updated!!
How to check if it is properly created?
Print your tree in in-order and see whether the in-order produces the data in sorted order or not.
How to calculate the Sum of Nodes
Steps for in Searching the data specifically
Searching in BST Code:
IF you are searching in arbitary binary tree( regular binary tree)
You would need to check one of the traversal methods(pre, in, and post order), and checking each node in the process. Won’t be O(log n) anymore, degenerates to O(n);
Deletion with Binary Trees
Three ways, one deleting a leaf node, another, deleting a node with one child, and deleting a node with two children.
first way)
keep going for one child)
deleting a node with two children )either chose the largest value on the left subtree, or thje smallest value on the right subtree, in essence, picking either the rightmost value on the left subtree, or the leftmost value on the right subtree.
left max, right min.
A lot going on for deletion of a node with two children, every aux function used.
FindNode
Parent
Min Val
MaxVal
isLeaf
has OnlyLeftChild
HasOnlyRightChild
Extra
Okay, from this 1, 3, 4, 6, 7, 8, 10, 13, 14.
With the predecessor of 8 - 7 and the successor of 8 - 10(the one that would take it’s place from the left(pre) and the right subtree.
with replacing for predecessor, it deletes 7, keeping the value, and then it replaces the data of 8 with 7.
With replacing for successor, with 10, it is a node with one child, so it needs to do in this order
delete 8 (value)
delete 10
// by skipping 10, it effectively deletes it, so now 8 points to 14
finally it replaces the value of 8 with 10.
Implementation
// Part of this code credits to Mr. Guha and Dr. Ahmed
#include <stdio.h>
#include <stdlib.h>
// Define the structure of a tree node
typedef struct node_s {
int data;
struct node_s *leftchild;
struct node_s *rightchild;
} treenode_t;
// Function prototypes
treenode_t *createNode(int val);
treenode_t *insertR(treenode_t *root, int val);
treenode_t *removeNode(treenode_t *root, int val);
treenode_t *search(treenode_t *root, int val);
void inorder(treenode_t *root);
void postorder(treenode_t *root);
void preorder(treenode_t *root);
void destroyTree(treenode_t *root);
treenode_t *findNode(treenode_t *current_ptr, int value);
treenode_t *parent(treenode_t *root, treenode_t *node);
treenode_t *minVal(treenode_t *root);
treenode_t *maxVal(treenode_t *root);
int isLeaf(treenode_t *node);
int hasOnlyLeftChild(treenode_t *node);
int hasOnlyRightChild(treenode_t *node);
int main() {
// Initialize an empty BST
treenode_t *root = NULL;
// Insert hardcoded values into the BST
root = insertR(root, 50);
root = insertR(root, 30);
root = insertR(root, 70);
root = insertR(root, 20);
root = insertR(root, 40);
root = insertR(root, 60);
root = insertR(root, 80);
printf("Binary Search Tree created with hardcoded values.\n");
// Perform different tree traversals
printf("Inorder Traversal: ");
inorder(root);
printf("\n");
printf("Preorder Traversal: ");
preorder(root);
printf("\n");
printf("Postorder Traversal: ");
postorder(root);
printf("\n");
// Search for a value in the BST
int searchVal = 40;
if (search(root, searchVal))
printf("Value %d found in the BST.\n", searchVal);
else
printf("Value %d not found in the BST.\n", searchVal);
// Remove a node from the BST
printf("Removing value 30 from the BST.\n");
root = removeNode(root, 30);
// Inorder traversal after deletion
printf("Inorder Traversal after deletion: ");
inorder(root);
printf("\n");
// Free the allocated memory for BST
destroyTree(root);
printf("Binary Search Tree destroyed.\n");
return 0;
}
// Function to create a new tree node
treenode_t *createNode(int val) {
treenode_t *node = (treenode_t *)malloc(sizeof(treenode_t));
if (node == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}
node->data = val;
node->leftchild = NULL;
node->rightchild = NULL;
return node;
}
// // Recursive function to insert a node into the BST - more clean code (compact)
// treenode_t *insertR(treenode_t *root, int val) {
// if (root == NULL) {
// return createNode(val);
// }
// if (val < root->data) {
// root->leftchild = insertR(root->leftchild, val);
// } else {
// root->rightchild = insertR(root->rightchild, val);
// }
// return root;
// }
// longer version to insert a node
treenode_t *insertR(treenode_t *root, int val) {
// Case 1: The tree is empty — create and return a new node.
if (root == NULL) {
printf("Element data %d -> address: %p\n", val, &val);
return createNode(val);
}
else {
// Case 2: Value should go to the left subtree.
if (val < root->data) {
// If the left child exists, recurse into that subtree.
if (root->leftchild != NULL)
root->leftchild = insertR(root->leftchild, val);
// Otherwise, create a new node and link it to the left.
else
root->leftchild = createNode(val);
}
// Case 3: Value should go to the right subtree.
else {
// If the right child exists, recurse into that subtree.
if (root->rightchild != NULL)
root->rightchild = insertR(root->rightchild, val);
// Otherwise, create a new node and link it to the right.
else
root->rightchild = createNode(val);
}
// Return the (unchanged) root pointer after insertion.
return root;
}
}
// Recursive function to search for a node in the BST
treenode_t *search(treenode_t *root, int val) {
if (root == NULL || root->data == val) {
return root;
} else if (val < root->data) {
return search(root->leftchild, val);
} else {
return search(root->rightchild, val);
}
}
// Find a node storing value in the subtree rooted at current_ptr - this is very similar to
// the search function we wrote above
treenode_t *findNode(treenode_t *current_ptr, int value) {
if (current_ptr == NULL) return NULL;
if (current_ptr->data == value)
return current_ptr;
if (value < current_ptr->data)
return findNode(current_ptr->leftchild, value);
return findNode(current_ptr->rightchild, value);
}
// Return the parent of node in the tree rooted at root (or NULL if none/root not found).
treenode_t *parent(treenode_t *root, treenode_t *node) {
if (root == NULL || root == node)
return NULL;
if (root->leftchild == node || root->rightchild == node)
return root;
if (node->data < root->data)
return parent(root->leftchild, node);
if (node->data > root->data)
return parent(root->rightchild, node);
return NULL;
}
// Minimum value node in a (non-empty) subtree
treenode_t *minVal(treenode_t *root) {
if (root == NULL)
return NULL;
if (root->leftchild == NULL)
return root;
return minVal(root->leftchild);
}
// Maximum value node in a (non-empty) subtree
treenode_t *maxVal(treenode_t *root) {
if (root == NULL)
return NULL;
if (root->rightchild == NULL)
return root;
return maxVal(root->rightchild);
}
int isLeaf(treenode_t *node) {
return (node != NULL && node->leftchild == NULL && node->rightchild == NULL);
}
int hasOnlyLeftChild(treenode_t *node) {
return (node != NULL && node->leftchild != NULL && node->rightchild == NULL);
}
int hasOnlyRightChild(treenode_t *node) {
return (node != NULL && node->leftchild == NULL && node->rightchild != NULL);
}
// Delete the node storing val in the BST rooted at root
// Returns the (possibly new) root after deletion.
treenode_t *removeNode(treenode_t *root, int val) {
treenode_t *delnode = findNode(root, val);
if (delnode == NULL) {
// Value not found; return root unchanged.
return root;
}
treenode_t *par = parent(root, delnode);
// Case 1: leaf node
if (isLeaf(delnode)) {
if (par == NULL) { // deleting the only node (root)
free(root);
return NULL;
}
if (val < par->data) { // delnode is left child
free(par->leftchild);
par->leftchild = NULL;
} else { // delnode is right child
free(par->rightchild);
par->rightchild = NULL;
}
return root;
}
// Case 2-a: only left child
if (hasOnlyLeftChild(delnode)) {
if (par == NULL) { // deleting root
treenode_t *save = delnode->leftchild;
free(delnode);
return save;
}
if (val < par->data) { // delnode is left child
treenode_t *save = par->leftchild;
par->leftchild = par->leftchild->leftchild;
free(save);
} else { // delnode is right child
treenode_t *save = par->rightchild;
par->rightchild = par->rightchild->leftchild;
free(save);
}
return root;
}
// Case 2-b: only right child
if (hasOnlyRightChild(delnode)) {
if (par == NULL) { // deleting root
treenode_t *save = delnode->rightchild;
free(delnode);
return save;
}
if (val < par->data) { // delnode is left child
treenode_t *save = par->leftchild;
par->leftchild = par->leftchild->rightchild;
free(save);
} else { // delnode is right child
treenode_t *save = par->rightchild;
par->rightchild = par->rightchild->rightchild;
free(save);
}
return root;
}
// Case 3: two children
// If your code reaches hear it means delnode has two children
// Find the new physical node to delete.
treenode_t *new_del_node = minVal(delnode->rightchild);
int save_val = new_del_node->data;
root = removeNode(root, save_val); // delete the successor node
delnode->data = save_val; // put minVal value into original node
return root;
}
// Function to remove a node from the BST - Note that this code is more compact than the previous one but they
// both works the same
// treenode_t *removeNode(treenode_t *root, int val) {
// if (root == NULL) {
// printf("Node doesn't exist.\n");
// return root;
// }
// if (val < root->data) {
// root->leftchild = removeNode(root->leftchild, val);
// }
// else if (val > root->data) {
// root->rightchild = removeNode(root->rightchild, val);
// }
// else {
// // Case 1: No child
// if (root->leftchild == NULL && root->rightchild == NULL) {
// free(root);
// return NULL;
// }
// // Case 2: One child (right child exists)
// else if (root->leftchild == NULL) {
// treenode_t *temp = root->rightchild;
// free(root);
// return temp;
// }
// // Case 2: One child (left child exists)
// else if (root->rightchild == NULL) {
// treenode_t *temp = root->leftchild;
// free(root);
// return temp;
// }
// // Case 3: Two children
// treenode_t *temp = minVal(root->rightchild); // successor
// root->data = temp->data;
// root->rightchild = removeNode(root->rightchild, temp->data);
// }
// return root;
// }
// Function to perform an inorder traversal (Left, Root, Right)
void inorder(treenode_t *root) {
if (root != NULL) {
inorder(root->leftchild);
printf("%d ", root->data);
inorder(root->rightchild);
}
}
// Function to perform a preorder traversal (Root, Left, Right)
void preorder(treenode_t *root) {
if (root != NULL) {
printf("%d ", root->data);
preorder(root->leftchild);
preorder(root->rightchild);
}
}
// Function to perform a postorder traversal (Left, Right, Root)
void postorder(treenode_t *root) {
if (root != NULL) {
postorder(root->leftchild);
postorder(root->rightchild);
printf("%d ", root->data);
}
}
// Function to deallocate all nodes in the tree
void destroyTree(treenode_t *root) {
if (root != NULL) {
destroyTree(root->leftchild);
destroyTree(root->rightchild);
free(root);
}
}
Second Implementation by Guha(first was Ahmed)
// Arup Guha
// 3/25/04, with code added to do delete on 3/30/04
// COP 3502 Lecture: Some Binary Tree Functions
#include <stdio.h>
#include <stdlib.h>
struct tree_node {
int data;
struct tree_node *left;
struct tree_node *right;
};
struct tree_node *create_node(int val);
void inorder(struct tree_node *current_ptr);
struct tree_node* insert(struct tree_node *root,
struct tree_node *element);
int add(struct tree_node *current_ptr);
int find(struct tree_node *current_ptr, int val);
struct tree_node* parent(struct tree_node *root, struct tree_node *node);
struct tree_node* minVal(struct tree_node *root);
struct tree_node* maxVal(struct tree_node *root);
int isLeaf(struct tree_node *node);
int hasOnlyLeftChild(struct tree_node *node);
int hasOnlyRightChild(struct tree_node *node);
struct tree_node* findNode(struct tree_node *current_ptr, int value);
struct tree_node* delete(struct tree_node* root, int value);
// struct tree_node* q6(struct tree_node* root, int x);
void what(struct tree_node *root, int val);
int numnodes(struct tree_node* root);
int findKthSmallest(struct tree_node* root, int k);
int menu();
int main() {
struct tree_node *my_root=NULL, *temp_node;
int done = 0,ans=1, val, q6data;
ans = menu();
while (ans<8) {
if (ans == 1) {
// Get value to insert.
printf("What value would you like to insert?");
scanf("%d", &val);
temp_node = create_node(val); // Create the node.
// Insert the value.
my_root = insert(my_root, temp_node);
}
if (ans == 2) {
printf("What value would you like to delete?\n");
scanf("%d", &val);
if (!find(my_root, val))
printf("Sorry that value isn't in the tree to delete.\n");
else {
my_root = delete(my_root, val);
}
}
if (ans == 3) {
printf("What value would you like to search for?\n");
scanf("%d", &val);
if (find(my_root, val))
printf(" Found %d in the tree.\n", val);
else
printf(" Did not find %d in the tree.\n", val);
}
if (ans == 4)
printf("The sum of the nodes in your tree is %d.\n", add(my_root));
if (ans == 5) {
// Print the resulting tree.
printf("Here is an inorder traversal of your tree: ");
inorder(my_root);
printf("\n");
}
if (ans == 6) {
printf("Exiting...\n");
return 0;
}
// if (ans == 7) {
// // Print the resulting tree.
// printf("enter a value for q6: ");
// scanf("%d", &q6data);
// printf("Q6: ");
// // q6(my_root, q6data );
// printf("\n");
// }
// See if they want to insert more nodes.
ans = menu();
}
/*
printf("Testing what function.\n\n");
what(my_root, 7);
printf("\n");
*/
int rank;
printf("Which ranked item would you like to find?\n");
scanf("%d", &rank);
printf("The item is %d\n", findKthSmallest(my_root, rank));
system("PAUSE");
return 0;
}
void inorder(struct tree_node *current_ptr) {
// Only traverse the node if it's not null.
if (current_ptr != NULL) {
inorder(current_ptr->left); // Go Left.
printf("%d ", current_ptr->data); // Print the root.
inorder(current_ptr->right); // Go Right.
}
}
struct tree_node* insert(struct tree_node *root,
struct tree_node *element) {
// Inserting into an empty tree.
if (root == NULL){
printf("Element data %d -> address: %p\n", element->data, &(element->data));
return element;
}
else {
// element should be inserted to the right.
if (element->data > root->data) {
// There is a right subtree to insert the node.
if (root->right != NULL)
root->right = insert(root->right, element);
// Place the node directly to the right of root.
else
root->right = element;
}
// element should be inserted to the left.
else {
// There is a left subtree to insert the node.
if (root->left != NULL)
root->left = insert(root->left, element);
// Place the node directly to the left of root.
else
root->left = element;
}
// Return the root pointer of the updated tree.
return root;
}
}
struct tree_node* create_node(int val) {
// Allocate space for the node, set the fields.
struct tree_node* temp;
temp = (struct tree_node*)malloc(sizeof(struct tree_node));
temp->data = val;
temp->left = NULL;
temp->right = NULL;
return temp; // Return a pointer to the created node.
}
int find(struct tree_node *current_ptr, int val) {
// Check if there are nodes in the tree.
if (current_ptr != NULL) {
// Found the value at the root.
if (current_ptr->data == val)
return 1;
// Search to the left.
if (val < current_ptr->data)
return find(current_ptr->left, val);
// Or...search to the right.
else
return find(current_ptr->right, val);
}
else
return 0;
}
void what(struct tree_node *root, int val) {
if (root != NULL) {
if (root->data > val)
printf("%d ", root->data+val);
if (root->data%val > 5)
what(root->left, val+3);
else
what(root->right, val+4);
}
}
int add(struct tree_node *current_ptr) {
if (current_ptr != NULL)
return current_ptr->data+add(current_ptr->left)+
add(current_ptr->right);
else
return 0;
}
// Returns the parent of the node pointed to by node in the tree rooted at
// root. If the node is the root of the tree, or the node doesn't exist in
// the tree, null will be returned.
struct tree_node* parent(struct tree_node *root, struct tree_node *node) {
// Take care of NULL cases.
if (root == NULL || root == node)
return NULL;
// The root is the direct parent of node.
if (root->left == node || root->right == node)
return root;
// Look for node's parent in the left side of the tree.
if (node->data < root->data)
return parent(root->left, node);
// Look for node's parent in the right side of the tree.
else if (node->data > root->data)
return parent(root->right, node);
return NULL; // Catch any other extraneous cases.
}
// Returns a pointer to the node storing the minimum value in the tree
// with the root, root. Will not work if called with an empty tree.
struct tree_node* minVal(struct tree_node *root) {
// Root stores the minimal value.
if (root->left == NULL)
return root;
// The left subtree of the root stores the minimal value.
else
return minVal(root->left);
}
// Returns a pointer to the node storing the maximum value in the tree
// with the root, root. Will not work if called with an empty tree.
struct tree_node* maxVal(struct tree_node *root) {
// Root stores the maximal value.
if (root->right == NULL)
return root;
// The right subtree of the root stores the maximal value.
else
return maxVal(root->right);
}
// Returns 1 if node is a leaf node, 0 otherwise.
int isLeaf(struct tree_node *node) {
return (node->left == NULL && node->right == NULL);
}
// Returns 1 iff node has a left child and no right child.
int hasOnlyLeftChild(struct tree_node *node) {
return (node->left!= NULL && node->right == NULL);
}
// Returns 1 iff node has a right child and no left child.
int hasOnlyRightChild(struct tree_node *node) {
return (node->left== NULL && node->right != NULL);
}
// Returns a pointer to a node that stores value in it in the subtree
// pointed to by current_ptr. NULL is returned if no such node is found.
struct tree_node* findNode(struct tree_node *current_ptr, int value) {
// Check if there are nodes in the tree.
if (current_ptr != NULL) {
// Found the value at the root.
if (current_ptr->data == value)
return current_ptr;
// Search to the left.
if (value < current_ptr->data)
return findNode(current_ptr->left, value);
// Or...search to the right.
else
return findNode(current_ptr->right, value);
}
else
return NULL; // No node found.
}
// Will delete the node storing value in the tree rooted at root. The
// value must be present in the tree in order for this function to work.
// The function returns a pointer to the root of the resulting tree.
struct tree_node* delete(struct tree_node* root, int value) {
struct tree_node *delnode, *new_del_node, *save_node;
struct tree_node *par;
int save_val;
delnode = findNode(root, value); // Get a pointer to the node to delete.
par = parent(root, delnode); // Get the parent of this node.
// Take care of the case where the node to delete is a leaf node.
if (isLeaf(delnode)) {// case 1
// Deleting the only node in the tree.
if (par == NULL) {
free(root); // free the memory for the node.
return NULL;
}
// Deletes the node if it's a left child.
if (value < par->data) {
free(par->left); // Free the memory for the node.
par->left = NULL;
}
// Deletes the node if it's a right child.
else {
free(par->right); // Free the memory for the node.
par->right = NULL;
}
return root; // Return the root of the new tree.
}
// Take care of the case where the node to be deleted only has a left
// child.
if (hasOnlyLeftChild(delnode)) {
// Deleting the root node of the tree.
if (par == NULL) {
save_node = delnode->left;
free(delnode); // Free the node to delete.
return save_node; // Return the new root node of the resulting tree.
}
// Deletes the node if it's a left child.
if (value < par->data) {
save_node = par->left; // Save the node to delete.
par->left = par->left->left; // Readjust the parent pointer.
free(save_node); // Free the memory for the deleted node.
}
// Deletes the node if it's a right child.
else {
save_node = par->right; // Save the node to delete.
par->right = par->right->left; // Readjust the parent pointer.
free(save_node); // Free the memory for the deleted node.
}
return root; // Return the root of the tree after the deletion.
}
// Takes care of the case where the deleted node only has a right child.
if (hasOnlyRightChild(delnode)) {
// Node to delete is the root node.
if (par == NULL) {
save_node = delnode->right;
free(delnode);
return save_node;
}
// Delete's the node if it is a left child.
if (value < par->data) {
save_node = par->left;
par->left = par->left->right;
free(save_node);
}
// Delete's the node if it is a right child.
else {
save_node = par->right;
par->right = par->right->right;
free(save_node);
}
return root;
}
//if your code reaches hear it means delnode has two children
// Find the new physical node to delete.
new_del_node = minVal(delnode->right);
save_val = new_del_node->data;
delete(root, save_val); // Now, delete the proper value.
// Restore the data to the original node to be deleted.
delnode->data = save_val;
return root;
}
// /*** NEW FUNCTION ADDED - EDIT AND PUT IN FRAMEWORK ***/
// struct tree_node* q6(struct tree_node* root, int x) {
// if (root == NULL)
// return NULL;
// if (root->data > x) {
// struct treenode* tmp = q6(root->left, x);
// if (tmp == NULL)
// {
// printf("root: %d", root->data);
// return root;
// }
// else
// {
// printf("tmp: %d", tmp->data);
// return tmp;
// }
// }
// else
// return q6(root->right, x);
// }
// Returns the number of nodes in the tree pointed to by root.
int numnodes(struct tree_node* root) {
if (root == NULL) return 0;
return 1 + numnodes(root->left) + numnodes(root->right);
}
// Guaranteed that k is in between 1 and the number of nodes in the tree
// pointed to by root.
int findKthSmallest(struct tree_node* root, int k) {
int numNodesLeft = numnodes(root->left);
if (numNodesLeft >= k)
return findKthSmallest(root->left, k);
else if (numNodesLeft == k-1)
return root->data;
else
return findKthSmallest(root->right, k-numNodesLeft-1);
}
// Prints out the menu of choices for the user and returns their choice.
int menu() {
int ans;
printf("Here are your choices.\n");
printf("1. Insert an item into your tree.\n");
printf("2. Delete an item from your tree.\n");
printf("3. Search for an item in your tree.\n");
printf("4. Print the sum of the nodes in your tree.\n");
printf("5. Print out an inorder traversal of your tree.\n");
// printf("7. Call Q6.\n");
printf("6. Quit.\n");
scanf("%d", &ans);
return ans;
}