I am working on a school project where we have to implement a polymorphic binary search tree that instead of using null references to "empty" parts of the tree, uses two classes (NonEmptyTree and EmptyTree) that you are supposed to use polymorphism to work out when certain actions should take place.

For example, if I want to insert a particular key value in a non-polymorphic Binary Search Tree, typically you could just recursively compare against null as you move through your tree, sticking in your value whenever you get a compareTo value of 0. However in this case, because of the design of this EmptyTree class (there is only one instance of it), you are essentially forbidden from actively comparing against "EmptyTree.getInstance()" which "frees up" the single instance of EmptyTree. (getInstance() is a static method).

I am attaching a link to the two classes with the code I have written so far. I think Pastebin's syntax highlighting is much easier to read than inserting all my code in here, so hopefully this is OK.

I am not looking for solutions or any major giveaways, but I am extremely frustrated because it seems illogical to implement the tree this way. (I have already implemented a fairly complete BST with null references, but it seems this exercise was pointless as I have no idea how to move forward). In addition, this is not due until next Sunday so my anger is not at all the result of procrastination but rather intellectual frustration at my sense of personal inadequacy.

Any insight is appreciated.

The NonEmptyTree class: http://pastebin.com/

The EmptyTree class: http://pastebin.com/

As you can see, I make extensive use of the EmptyTree.getInstance() method as it seems like a more or less efficient way to check whether or not I should instantiate a new NonEmptyList to stick in that place. However, the Professor's words in the project specification specifically state: "You are expected to use polymorphism (and exception handling, where appropriate) to handle the differences between empty and nonempty trees. Failure to do so will result in a large negative adjustment to your project grade."

However, I feel like these instructions contradict his lectures last semester where the message was "never ever EVER use exception handling for "control-flow", i.e. misusing catching exceptions as a way to control the behavior of the code." Even the single method that I wrote which uses a try-catch block to return a Tree feels like blasphemy.

You might consider this a "solution" or "major giveaway" but...

I agree this seems kind of silly, at least in Java.

The idea, though, is probably to have your `EmptyTree`

and `NonEmptyTree`

classes inherit from some sort of `PossiblyEmptyTree`

base class, and then override methods differently in each to achieve the correct behaviour without the caller knowing (or checking) if the `PossiblyEmptyTree`

is empty or not (*i.e.* polymorphism).

Some code that might appear in your solution:

```
public class EmptyTree ... {
...
public V search(K key) {
/* definitely not here! */
return null;
}
}
```

Similar Questions

Note: I've included the code for the insert in case that is where my error lies. I'm having trouble removing nodes in my binary search tree. I ran this through eclipse and the node's pointers seem t

First off, this is homework, so putting that out there. I'm supposed to implement a binary search tree with specific methods: void insert(String), boolean remove(String), and boolean find (String). I

My Binary Search Tree program doesn't seem to be deleting anything when I call the deleteNode method. The BST is built perfectly, its just deleting the node part that doesn't work. I call it from my m

I have followed this idea and this C++ code to reconstruct binary Search Tree from PreOrder array in Java. I am not reinventing the algorithm, but trying to implement pseudocode. I need help here. I d

I'm slightly confused about how the order of nodes can be arranged in a binary search tree. Can there be node of a subtree in a binary search tree on the left that is larger than the root node? For ex

I have a homework which ask from me to create a struct of binary search tree where its node of the binary search tree is another binary search tree. The first BST has the Surnames of Students and the

I had a question of exactly how a binary search tree of strings works. I know and have implemented binary search trees of integers by checking if the new data <= parent data then by branching left

I am trying to figure out how to remove a node from a binary search tree, I understand that it is different for each node whether it is a leaf, has one child or two children. So as of now my function

I have problem with method MoveNext in my enumerator. I need iterator for binary search tree. In construcotr of my enumerator I initialize Node to root of tree. Current is value that I ened to return

I am trying to traverse a binary search tree in-order, and place the data (sorted) in an array. for some reason, the pointer to the current position in the array is not moving right. This is the decle

Need help to figure out why the following code for basic Binary Search Tree insertion is not working. Since I have been working on C# for sometime now, I'm afraid I forgot some of my C++. Also, any su

I am trying to create a module in python for iterating over a binary tree using the 4 standard tree traversals (inorder, preorder, postorder and levelorder) without using conditionals and only using p

I have a binary tree of node containing an integer and a char. I'm working on Huffman Coding and I want to get the binary presentation of the nodes. A '0' is appended to the string for every left bran

I was trying to implement binary search tree but I think I have made a mistake in my insert function. Here's my code #include<iostream> #include<memory.h> #include <cstddef> using na

I'm trying to search for a node in a binary tree and return in case it's there, otherwise, return null. By the way, the node class has a method name() that return a string with it's name...What I have

I'm creating Binary Search Tree class I got all my functions working accept the Successor. My tree input is 30 10 45 38 20 50 25 33 8 12 When I print Inorder traversal it come up as 8 10 12 20 25 30

I need to create a function that creates a BST from an array, in python. The array is already sorted. The example is: function array_to_binary_search_tree(array, start, end) if start > end Return a

I'm scouring the internet for a definition of the term Internal Node. I cannot find a succinct definition. Every source I'm looking at uses the term without defining it, and the usage doesn't yield

Hello i need to make a function that inserts a new node into a binary search tree and returns a pointer to the head/root of that tree. My problem is with the returned value, i cant seem to figure out

Here's the node definition: struct node{ int data; stuct node * left; struct node * right; }; What I am trying to do is list all the nodes that point to an ancestor node. After posting the wrong solu

Got nothing better to do this Christmas holiday, so I decided to try out making a binary search tree. I'm stuck with the print function. How should the logic behind it work? Since the tree is already

So here is the Node class: public class Node { private int _info; private Node _left; private Node _right; public Node() { //this._info = Integer.MIN_VALUE; this._left = null; this._right = null; } pu

So I'm trying to insert a value into a binary tree using this recursive function: void add(node* *hd, int v){ node* curr = *hd; if(curr == NULL){ curr = (node*)malloc(sizeof(node)); curr->value = v

I have two functions in a class that creates a binary tree: void Btree::insertNode(node* r, node* newNode){ if (r == NULL) r = newNode; else if (greater(root, newNode)) insertNode(r->left, newNode)

want to insert element in binary tree. what is wrong in this code. I have a structure with data, left and right as self referencing structure and root as a global variable of type structure initialize

I'm trying to implement a Binary tree (is not important if it's general binary tree, or binary search tree) and I'm having some troubles with the function that creates a node and link it into the tree

This question already has an answer here: How do you validate a binary search tree? 18 answers Given a simple binary tree, how can we prove that tree is a binary search tree? When we traverse a

I have to write a non recursive program to print the ancestor (parent of parent) of a given node in a Binary Tree. What logic should I use ?

I'm currently implementing a red-black binary search tree for geometric interval search. I'm saving in the tree segments containing a startpoint and a endpoinit where the startpoint is the key entry t

I have 2 classes, NonEmptyTree and EmptyTree that implement the Tree interface. toString() method in NonEmptyTree class should return a string: key=>value key=>value key>value etc... I do not

I have a problem that I need to complete: We can represent a nonempty binary tree by list (root left_subtree right_subtree) and the empty tree by the empty list. Each binary search tree with integer

Recently, I'm trying to solve all the exercises in CLRS. but there are some of them i can't figure out. Here is one of them, from CLRS exercise 12.4-2: Describe a binary search tree on n nodes such

If I delete node x and then node y or delete y and the x, after this deleted I will stay with the same binary search tree? I tried a few examples and I think that's true. But how can i prove this?

Anyone could help me do this: I need a public method for my binary search tree ADT that returns a reference to the information in the node with the smallest value in the tree. The signature of the met

I am studying Breadth First Search , and wanted to ask that Is the Tree constructed by Breadth First Search ( the BFS tree, wherein we store each node's predecessor) a Binary Tree?

I am trying to do a search operation in BT. For example: 3 (Root) 5 1 6 2 0 8 This is my BT and this is the code I have written for search. Node* search(Node *root,int key) { if(root) { if(root->

Well i build a basic Binary Search Tree using a class called Node for simplicity i will include the core method that is used to insert Nodes public function addNode($node) { if ($this->left == null

I'm using OCaml. I have type: type 'a bt = Empty | Node of 'a * 'a bt * 'a bt;; Also I have example BST: let tree = Node(1,Node(2,Node(4,Empty,Empty),Empty),Node(3,Node(5,Empty,Node(6,Empty,Empty)),

I have a binary tree with the only condition that there is a single node in the deepest level. The nodes in the tree have the parent property (as well as left, right, data) Is it possible to determine

I am working on a function that searches a templated binary search tree for a value with a given key and then returns a pointer to that data value. If the given key doesn't exist in the tree, the poin

Hi i'm creating an algorithm for a binary tree for uni work and I need to develop an algorithm that efficiently find all the values smaller than a specified value (they need to be in order). 10 / \ 9

I have a binary tree where each node can have a value. I want to find the node in the tree that has value null and is closest to the root. If there are two nodes with the same distance from the root,

I would like to know some complexities of binary search tree, I can't find complete information. I want to know complexities for this operations on a binary search tree 1) to add/insert an element 2)

Two BSTs (Binary Search Trees) are given. How to find largest common sub-tree in the given two binary trees? EDIT 1: Here is what I have thought: Let, r1 = current node of 1st tree r2 = current node o

My linked list structure is typedef struct ll { int data; struct ll *left; struct ll *right; }node; My function for deleting is void delete(node **parent,node **root,int n) { if((*root)==NULL) //if

I want to find the deepest element of a binary tree, So far the code only works for empty tree or the height is one. Here is the code My height function works correctly. deepest(node(L,X,R),X):- heig

My partner and I are implementing a Binary Search Tree for a Data Structures & Algorithms course. We are encountering issues with our add method. This code is shown below: public class BinarySearc

Do you know, please, if C++ STL contains a Binary Search Tree (BST) implementation, or if I should construct my own BST object? In case STL conains no implementation of BST, are there any libraries av

Can anyone point out a way of getting the depth of a Node in a Binary Tree (not a balanced one, or BST) without using recursion? Ideally in Java/C/C# The node is represented as: class Node { Node Left

I'm having trouble writing code to determine if certain data is present in my tree, this is the BinaryTreeNode class class BinaryTreeNode { public: Data * nodeData; BinaryTreeNode * left; BinaryTreeNo