Binary Search Trees in C#
Binary search trees are an important data structure in computer science. They are used to store and organize data in a fast and efficient manner. In this article, we will discuss the fundamentals of binary search trees, how to implement them in C#, and the time and space complexity involved. We will also look at some coding exercises to test your understanding.
What is a Binary Search Tree?
A binary search tree (BST) is a type of tree data structure in which each node has at most two children, and the left subtree of each node contains only nodes with values less than the node’s value, while the right subtree of each node contains only nodes with values greater than the node’s value.
The root node of a BST can be thought of as the entry point into the tree. All nodes in the left subtree of the root node have a value that is less than the root node’s value, while all nodes in the right subtree of the root node have a value that is greater than the root node’s value. This is known as the BST property.
Adding Nodes to a Binary Search Tree
When adding a node to a binary search tree, we must first find the place in the tree where it should be inserted. To do this, we start at the root node and compare the value of the node we are inserting with the value of the root node. If the value is less than the root node’s value, we move to the left subtree and continue this process until we find an empty spot. If the value is greater than the root node’s value, we move to the right subtree and continue this process until we find an empty spot.
In C#, we can use the following code to insert a node with a value of x into a BST.
// Recursive function to insert a node with a value of x
public void Insert(int x)
{
// If the tree is empty
if (root == null)
root = new Node(x);
else // If the tree is not empty
Insert(root, x);
}
// Recursive function to insert a node with a value of x
public void Insert(Node root, int x)
{
// If the value of x is less than the value of the root node
if (x < root.data)
{
// If the left child is null
if (root.left == null)
root.left = new Node(x);
else // If the left child is not null
Insert(root.left, x);
}
// If the value of x is greater than the value of the root node
else if (x > root.data)
{
// If the right child is null
if (root.right == null)
root.right = new Node(x);
else // If the right child is not null
Insert(root.right, x);
}
}
Searching a Binary Search Tree
Searching a binary search tree is similar to inserting a node into a binary search tree. We start at the root node and compare the value of the node we are searching for with the value of the root node. If the value is less than the root node’s value, we move to the left subtree and continue this process until we find the node we are searching for. If the value is greater than the root node’s value, we move to the right subtree and continue this process until we find the node we are searching for.
In C#, we can use the following code to search for a node with a value of x in a BST.
// Recursive function to search for a node with a value of x
public Node Search(int x)
{
// If the tree is empty
if (root == null)
return null;
else // If the tree is not empty
return Search(root, x);
}
// Recursive function to search for a node with a value of x
public Node Search(Node root, int x)
{
// If the value of x is equal to the value of the root node
if (x == root.data)
return root;
// If the value of x is less than the value of the root node
else if (x < root.data)
{
// If the left child is null
if (root.left == null)
return null;
else // If the left child is not null
return Search(root.left, x);
}
// If the value of x is greater than the value of the root node
else
{
// If the right child is null
if (root.right == null)
return null;
else // If the right child is not null
return Search(root.right, x);
}
}
Deleting Nodes from a Binary Search Tree
When deleting a node from a binary search tree, we must first find the node we want to delete. To do this, we start at the root node and compare the value of the node we want to delete with the value of the root node. If the value is less than the root node’s value, we move to the left subtree and continue this process until we find the node we want to delete. If the value is greater than the root node’s value, we move to the right subtree and continue this process until we find the node we want to delete.
Once we have found the node we want to delete, there are three cases to consider:
- The node is a leaf node. In this case, we simply delete the node and adjust the parent’s pointer.
- The node has one child. In this case, we delete the node and adjust the parent’s pointer to point to the node’s child.
- The node has two children. In this case, we must find the in-order successor of the node, which is the node with the next highest value in the tree. We then replace the node we want to delete with the in-order successor and delete the in-order successor.
In C#, we can use the following code to delete a node with a value of x from a BST.
// Recursive function to delete a node with a value of x
public void Delete(int x)
{
root = Delete(root, x);
}
// Recursive function to delete a node with a value of x
public Node Delete(Node root, int x)
{
// If the tree is empty
if (root == null)
return root;
// If the value of x is less than the value of the root node
if (x < root.data)
root.left = Delete(root.left, x);
// If the value of x is greater than the value of the root node
else if (x > root.data)
root.right = Delete(root.right, x);
// If the value of x is equal to the value of the root node
else
{
// If the node is a leaf node
if (root.left == null && root.right == null)
root = null;
// If the node has one child
else if (root.left == null)
root = root.right;
else if (root.right == null)
root = root.left;
// If the node has two children
else
{
// Find the in-order successor
Node temp = FindMin(root.right);
// Replace the root node's value with the in-order successor's value
root.data = temp.data;
// Delete the in-order successor
root.right = Delete(root.right, temp.data);
}
}
return root;
}
Time and Space Complexity
The time complexity of a binary search tree is dependent on the height of the tree. The height of a BST is the number of levels in the tree. If the tree is balanced (all levels have the same number of nodes), the height of the tree is log2N, where N is the number of nodes in the tree. If the tree is unbalanced, the height of the tree can be up to N.
The time complexity of access, search, insertion and deletion in a binary search tree is as follows:
- Access: O(log2N)
- Search: O(log2N)
- Insertion: O(log2N)
- Deletion: O(log2N)
The space complexity of a binary search tree is O(N), where N is the number of nodes in the tree.
Conclusion
In this article, we have discussed the fundamentals of binary search trees, how to implement them in C#, and the time and space complexity involved. We have also looked at some code examples to illustrate the concepts.
Exercises
Write a function to print out the values stored in a binary search tree in ascending order.
public void PrintInOrder(Node root)
{
// If the root node is not null
if (root != null)
{
// Recursively print the left subtree
PrintInOrder(root.left);
// Print the value of the root node
Console.Write(root.data + " ");
// Recursively print the right subtree
PrintInOrder(root.right);
}
}
Write a function to find the minimum value in a binary search tree.
public int FindMin(Node root)
{
// If the root node is null
if (root == null)
return -1;
// If the left child is null
else if (root.left == null)
return root.data;
// If the left child is not null
else
return FindMin(root.left);
}
Write a function to find the maximum value in a binary search tree.
public int FindMax(Node root)
{
// If the root node is null
if (root == null)
return -1;
// If the right child is null
else if (root.right == null)
return root.data;
// If the right child is not null
else
return FindMax(root.right);
}
Write a function to check if a given value is present in a binary search tree.
public bool Find(Node root, int x)
{
// If the root node is null
if (root == null)
return false;
// If the value of x is equal to the value of the root node
else if (x == root.data)
return true;
// If the value of x is less than the value of the root node
else if (x < root.data)
return Find(root.left, x);
// If the value of x is greater than the value of the root node
else
return Find(root.right, x);
}
Write a function to check if a given binary search tree is a valid binary search tree.
public bool IsValidBST(Node root)
{
// If the root node is null
if (root == null)
return true;
// If the left child is not null
if (root.left != null)
{
// If the left child's value is greater than the root node's value
if (root.left.data > root.data)
return false;
// Check the left subtree
else
return IsValidBST(root.left);
}
// If the right child is not null
if (root.right != null)
{
// If the right child's value is less than the root node's value
if (root.right.data < root.data)
return false;
// Check the right subtree
else
return IsValidBST(root.right);
}
// If none of the above conditions are true,
// then the binary search tree is a valid BST
return true;
}