Design and implement a C# class for a binary tree

Design and implement a C# class for a binary tree. The class should allow addition/removal of nodes as well as traversing the tree.

download code here













binary tree class:

using System;
using System.Collections.Generic;
using System.Text;

namespace BinaryTree
{
class TreeNode
{
private TreeNode leftNode; // link to left child
private int data; // data stored in node
private TreeNode rightNode; // link to right child

// initialize data and make this a leaf node
public TreeNode(int nodeData)
{
data = nodeData;
leftNode = rightNode = null; // node has no children
} // end constructor

// LeftNode property
public TreeNode LeftNode
{
get
{
return leftNode;
} // end get
set
{
leftNode = value;
} // end set
} // end property LeftNode

// Data property
public int Data
{
get
{
return data;
} // end get
set
{
data = value;
} // end set
} // end property Data

// RightNode property
public TreeNode RightNode
{
get
{
return rightNode;
} // end get
set
{
rightNode = value;
} // end set
} // end property RightNode

// insert TreeNode into Tree that contains nodes;
// ignore duplicate values
public void Insert(int insertValue)
{
if (insertValue < data) // insert in left subtree
{
// insert new TreeNode
if (leftNode == null)
leftNode = new TreeNode(insertValue);
else // continue traversing left subtree
leftNode.Insert(insertValue);
} // end if
else if (insertValue > data) // insert in right subtree
{
// insert new TreeNode
if (rightNode == null)
rightNode = new TreeNode(insertValue);
else // continue traversing right subtree
rightNode.Insert(insertValue);
} // end else if
} // end method Insert



} // end class TreeNode

// class Tree declaration
public class Tree
{
private TreeNode root;

// construct an empty Tree of integers
public Tree()
{
root = null;


} // end constructor

// Insert a new node in the binary search tree.
// If the root node is null, create the root node here.
// Otherwise, call the insert method of class TreeNode.
public void InsertNode(int insertValue)
{
if (root == null)
root = new TreeNode(insertValue);
else
root.Insert(insertValue);
} // end method InsertNode

// begin preorder traversal
public void PreorderTraversal()
{
PreorderHelper(root);
} // end method PreorderTraversal

// recursive method to perform preorder traversal
private void PreorderHelper(TreeNode node)
{
if (node == null)
return;

// output node data
Console.Write(node.Data + " ");

// traverse left subtree
PreorderHelper(node.LeftNode);

// traverse right subtree
PreorderHelper(node.RightNode);
} // end method PreorderHelper

// begin inorder traversal
public void InorderTraversal()
{
InorderHelper(root);
} // end method InorderTraversal

// recursive method to perform inorder traversal
private void InorderHelper(TreeNode node)
{
if (node == null)
return;

// traverse left subtree
InorderHelper(node.LeftNode);

// output node data
Console.Write(node.Data + " ");

// traverse right subtree
InorderHelper(node.RightNode);
} // end method InorderHelper

// begin postorder traversal
public void PostorderTraversal()
{
PostorderHelper(root);
} // end method PostorderTraversal

// recursive method to perform postorder traversal
private void PostorderHelper(TreeNode node)
{
if (node == null)
return;

// traverse left subtree
PostorderHelper(node.LeftNode);

// traverse right subtree
PostorderHelper(node.RightNode);

// output node data
Console.Write(node.Data + " ");
} // end method PostorderHelper

// delete node function
// this will check the root first.
// then try to search the delete value in the tree
// if the node is found, delete the node based on three consideration
// 1 Deleting a leaf
// 2 Deleting a node with one child
// 3 Deleting a node with two children
public void DeleteNode(int deleteValue)
{
if (root == null)
return;

// check the root data
// delete root node if its data equals to delete value
else if (root.Data == deleteValue)
{
if (root.LeftNode == null)
root = root.RightNode;
else if (root.RightNode == null)
root = root.LeftNode;

else if (root.LeftNode != null && root.RightNode != null)
{
int data = getPredecessor(root.LeftNode);
delRecNode(root.LeftNode, data);
root.Data = data;
}
}
else
{
delRecNode(root, deleteValue);
}



}
// recursive function to delete node based on value
private bool delRecNode(TreeNode node, int value)
{
if (node == null)
return false; // do nothing

if (value < node.Data)
{
if(delRecNode(node.LeftNode, value))
{
// There are several cases to be considered in deletion:
// case 1 no children
if (node.LeftNode.LeftNode == null && node.LeftNode.RightNode == null)
node.LeftNode = null;
// case 2 node has 1 child
else if (node.LeftNode.LeftNode == null)
node.LeftNode = node.LeftNode.RightNode;
else if (node.LeftNode.RightNode == null)
node.LeftNode = node.LeftNode.LeftNode;

// case 3 node has 2 children
else if (node.LeftNode.LeftNode != null && node.LeftNode.RightNode != null)
{
int data = getPredecessor(node.LeftNode.LeftNode);
// delete precessor
delRecNode(node.LeftNode.LeftNode, data);
node.LeftNode.Data = data;
}
}
return false;

}
else if (value > node.Data)
{

if(delRecNode(node.RightNode, value))
{
// There are several cases to be considered in deletion:
// case 1 no children
if (node.RightNode.LeftNode == null && node.RightNode.RightNode == null)
node.RightNode = null;

// case 2 node has 1 child
else if (node.RightNode.LeftNode == null)
node.RightNode = node.RightNode.RightNode;
else if (node.RightNode.RightNode == null)
node.RightNode = node.RightNode.LeftNode;

// case 3 node has 2 children
else if (node.RightNode.LeftNode != null && node.RightNode.RightNode != null)
{
int data = getPredecessor(node.RightNode.LeftNode);
// delete precessor
delRecNode(node.RightNode.LeftNode, data);
node.RightNode.Data = data;
}
}
return false;

}
else if (value == node.Data)
{
return true;
}
return false;

}
// get the value of predecessor
private int getPredecessor(TreeNode node)
{
if (node.RightNode != null)
{
return getPredecessor(node.RightNode);
}
else
{
return node.Data;
}

}

}
}