For this exercise you need to write up pseudocode for a Print method on the BinarySearchTree class. You will need to use a recursive approach, since this problem cannot be solved without the use of a stack (and recusion will get you a stack very conveniently)
This class is defined in the starter project for the POST Class Exercises, and is listed below for convenience. If you need more detail on any given method you should find the document/exercise in the PCEs which describes what the method in question should do.
For this exercise you need to write up pseudocode for each of the methods of the BinarySearchTree class that you'll be implementing during this week's PCEs using this document (note that the document also contains spaces for the remove method, which w
Be ready to present your pseudocode to the class, and to walk the class through your "trace".
public ErrorCode Remove(int target)
{
// if the tree is empty:
if (m_top == null)
return ErrorCode.OK;
else
return ErrorCode.DUPLICATE_VALUE_FOUND;
if (m_top.Data == target)
{
return RemoveRootNode(target);
}
else
{
return RemoveNonrootNode(target);
}
}
private ErrorCode RemoveNonrootNode(int target)
{
BSTNode cur = m_top;
BSTNode parent = null;
//First, find the target node that we need to remove
// we'll have the 'parent' reference trail the cur pointer down the tree
// so when we stop, cur is the node to remove, and parent is one above it.
while (false)
{
}
// Next, we figure out which of the cases we're in
// Case 1: The target node has no children
if (cur.Left == null && cur.Right == null)
{
return ErrorCode.OK;
}
// Case 2: The target node has 1 child
// (You may want to split out the left vs. right child thing)
// Case 3: The target node has 1 child
return ErrorCode.OK; // keep the compiler happy
}
private ErrorCode RemoveRootNode(int target)
{
// If we're here, it's because we're removing the top-most node (the 'root' node)
// Case 1: Root has no children
if (m_top.Left == null && m_top.Right == null)
{
m_top = null; // Therefore, the tree is now empty
return ErrorCode.OK;
}
// Case 2: Root has 1 child
else if (m_top.Left == null)
{
// 1 (right) child, OR zero children (right may also be null)
m_top = m_top.Right; // Right is null or another node - either way is correct
return ErrorCode.OK;
}
else if (m_top.Right == null)
{
// If we're here, Left is not null, so there MUST be one (Left) Child
m_top = m_top.Left;
return ErrorCode.OK;
}
// Case 3: Root has two children - this is where it gets interesting :)
else
{
// 2 children - find (and remove) next smaller value
// use that data to overwrite the current data.
BSTNode removee = FindAndRemoveNextSmallerValue(target, m_top);
m_top.Data = removee.Data;
return ErrorCode.OK;
}
}
/// <summary>
/// This method takes 1 step to the left, then walks as far to the right
/// as possible. Once that right-most node is found, it's removed & returned.
/// Note that the node MAY be immediately to the left of the <B>startHere</B>
/// parameter, if startHere.Left.Right == null
/// </summary>
/// <param name="smallerThanThis"></param>
/// <param name="startHere"></param>
/// <returns></returns>
private BSTNode FindAndRemoveNextSmallerValue(int smallerThanThis, BSTNode startHere)
{
BSTNode parent = startHere;
BSTNode child = startHere.Left;
return null;
}
The instructor will briefly outline how QuickSort works, and then have a Q + A session to pre-prepare you for the viewing quizzes & next week's topic.
Any remaining time will be spent working on any unfinished work: PCEs, homework assignments, revisions to homework assignments, etc
"A “one-minute paper” may be defined as a very short, in-class writing activity (taking one-minute or less to complete) in response to an instructor-posed question, which prompts students to reflect on the day’s lesson and provides the instructor with useful feedback." (from http://www.oncourseworkshop.com/Awareness012.htm).
For this One Minute Paper, I would like you to think back on both the preview videos / viewing quiz and today's in-class exercises, and quickly write up answers to two questions:
Head on over to the Google Docs form, and fill out the One Minute Paper for this lecture.