a Modified Binary Tree such that each node contains (at least) the following pro
ID: 3709884 • Letter: A
Question
a Modified Binary Tree such that each node contains (at least) the following properties:
public class BinaryTreeNode
{
public int data;
public BinaryTreeNode leftChild;
public BinaryTreeNode rightChild;
public BinaryTreeNode parent;
public BinaryTreeNode rightNode;
}
The Modified Binary Tree will use this Binary Tree Node to support the following:
1) The leftChild and rightChild pointers are used the same as an ordinary Binary Search Tree
2) The parent points to the parent BinaryTreeNode (if the BinaryTreeNode is root, parent is null)
3) The rightNode pointer points to the nearest Node to its right on the tree. This Node can either be a sibling or some other node that is on the same level. The far right node of a tree at any level should point to null.
This design modifies the standard Binary Search Tree. In the standard that we discussed in class, the left and right child pointers are such that the data value on the left of any Node is less than it and the data value on the right is greater. This standard remains for this Modified Binary Tree.
In addition, each Node can see (and thus, must maintain) the parent node. The complexity arises when also allowing each Node to see the next Node to its right on the same level (note that this can be the right sibling, first cousin, second cousin, etc.). The rightNode pointer allows us to basically have a Linked List at each level of the tree. For example:
6
4 8
2 7 9
1 3 10
Node 6: left = 4, right = 8, parent = null, rightNode = null
Node 4: left = 2, right = 7, parent = 6, rightNode = 8
Node 8: left = 7, right = 9, parent = 6, rightNode = null
Node 2: left = 1, right = 3, parent = 4, rightNode = 7
Node 3: left = null, right = null, parent = 2, rightNode = 10
...
Part 1) Complete the ModifiedBinaryTree class with the following functions:
public ModifiedBinaryTree()
public void insert(int n)
public boolean delete(int n)
public BinaryTreeNode getNode(int n)
public BinaryTreeNode getRightNode(BinaryTreeNode n)
public void printNode(int n)
public void printTree(…)
public void printLevel(int n)
The requirements for each function are as follows:
ModifiedBinaryTree():
This function is the default constructor for the Binary Tree and creates an empty tree
insert(int n):
This function inserts a new node into the tree. The insert algorithm is the same as a standard binary tree but you must also make sure to maintain the new node’s parent and rightNode pointers correctly
delete(int n):
This function deletes a node from the tree. The delete algorithm is the same as a standard binary tree but you must also make sure to maintain the correct pointers for all nodes that may be affected by the deletion. If the node is found and deleted, the function must return true, else return false
getNode(int n):
This function searches the tree for the node whose data property equals the given n. If the node is found, it returns the BinaryTreeNode. If the node is not found, the function returns null
getRightNode(BinaryTreeNode n):
This function returns the rightNode of the given BinaryTreeNode n. If there is no rightNode for the given node, the function must return null
printNode(int n):
This function searches the tree for a node with the given value n and prints all contents of the BinaryTreeNode. By printing, you must show the current data property and each BinaryTreeNode pointer property. For each BinaryTreeNode pointer, only show its data value. If the pointer is null, print “NULL”. For example, given the binary tree example on page 1 of this assignment, printNode(4) would display:
Data item: 4
leftChild: 2
rightChild: NULL
parent: 6
rightNode: 8
If you have other properties added to the BinaryTreeNode, you may want to show those property values as well (though these are minimum requirements)
printTree(…):
This function prints all the nodes in the tree. For each node that is printed, also print the level in which the node is in starting with the root node level as 1. For example, if the tree root value is 10 and has 2 children, 3 and 13, and 13 has one child with value of 15, printTree could show:
Level 1: 10
Level 2: 3
Level 2: 13
Level 3: 15
Note that the exact order of this example does not have to be followed as long as all 4 node values are shown with their correct level values
This function must also be written using recursion
printLevel(int n):
This function prints all the nodes of a tree on a given level (root level is 1) from left to right. For example, using the tree example on page 1 of this assignment, printLevel function calls would show the following:
printLevel(1): 6
printLevel(2): 4 8
printLevel(3): 2 7 9
printLevel(4): 1 3 10
Part 2) Write a main test program that allows the user to interactively test all these functions. The user must be able to insert, delete, search and print at any time similar to the way you wrote the main program for programming assignment 1. The demo of the program will be such that I will be testing to make sure everything works to my satisfaction.
When developing and testing this project, remember every change impacts may impact neighboring nodes, so you’ll want to test as many scenarios as you can predict.
Part 3) Analysis: At the conclusion of the demo, hand in a printout of an analysis answering these questions:
What is the Big-O performance category in the worst case of your insert, delete, getRightNode and printLevel functions using compare operations
There are different strategies to implementing this structure, particularly the getRightNode and printLevel methods. Based on how you did it, what is at least one other way you could have developed these methods different from how you coded it? Would the Big-O performance change significantly if you did so? If it is the same Big-O, is it better or worse within that category?
Do you think there are any uses for having the ability to show a level of a tree? If so, what are they and does your Big-O performance justify coding it the way you did?
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int largestBSTUtil(struct node* node, int *min_ref, int *max_ref,
int *max_size_ref, bool *is_bst_ref);
/* Returns size of the largest BST subtree in a Binary Tree
(efficient version). */
int largestBST(struct node* node)
{
// Set the initial values for calling largestBSTUtil()
int min = INT_MAX; // For minimum value in right subtree
int max = INT_MIN; // For maximum value in left subtree
int max_size = 0; // For size of the largest BST
bool is_bst = 0;
largestBSTUtil(node, &min, &max, &max_size, &is_bst);
return max_size;
}
/* largestBSTUtil() updates *max_size_ref for the size of the largest BST
subtree. Also, if the tree rooted with node is non-empty and a BST,
then returns size of the tree. Otherwise returns 0.*/
int largestBSTUtil(struct node* node, int *min_ref, int *max_ref,
int *max_size_ref, bool *is_bst_ref)
{
/* Base Case */
if (node == NULL)
{
*is_bst_ref = 1; // An empty tree is BST
return 0; // Size of the BST is 0
}
int min = INT_MAX;
/* A flag variable for left subtree property
i.e., max(root->left) < root->data */
bool left_flag = false;
/* A flag variable for right subtree property
i.e., min(root->right) > root->data */
bool right_flag = false;
int ls, rs; // To store sizes of left and right subtrees
/* Following tasks are done by recursive call for left subtree
a) Get the maximum value in left subtree (Stored in *max_ref)
b) Check whether Left Subtree is BST or not (Stored in *is_bst_ref)
c) Get the size of maximum size BST in left subtree (updates *max_size) */
*max_ref = INT_MIN;
ls = largestBSTUtil(node->left, min_ref, max_ref, max_size_ref, is_bst_ref);
if (*is_bst_ref == 1 && node->data > *max_ref)
left_flag = true;
/* Before updating *min_ref, store the min value in left subtree. So that we
have the correct minimum value for this subtree */
min = *min_ref;
/* The following recursive call does similar (similar to left subtree)
task for right subtree */
*min_ref = INT_MAX;
rs = largestBSTUtil(node->right, min_ref, max_ref, max_size_ref, is_bst_ref);
if (*is_bst_ref == 1 && node->data < *min_ref)
right_flag = true;
// Update min and max values for the parent recursive calls
if (min < *min_ref)
*min_ref = min;
if (node->data < *min_ref) // For leaf nodes
*min_ref = node->data;
if (node->data > *max_ref)
*max_ref = node->data;
/* If both left and right subtrees are BST. And left and right
subtree properties hold for this node, then this tree is BST.
So return the size of this tree */
if(left_flag && right_flag)
{
if (ls + rs + 1 > *max_size_ref)
*max_size_ref = ls + rs + 1;
return ls + rs + 1;
}
else
{
//Since this subtree is not BST, set is_bst flag for parent calls
*is_bst_ref = 0;
return 0;
}
}
/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(6);
root->left = newNode(4);
root->right = newNode(8);
root->left->left = newNode(2);
root->left->right = newNode(7);
root->right->left = newNode(7);
root->right->right = newNode(9);
root->left->left->left = newNode(11);
root->left->left->right = newNode(3);
root->right->right->right = newNode(10);
printf(" Size of the largest BST is %d", largestBST(root));
getchar();
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.