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:

1. The node is a leaf node. In this case, we simply delete the node and adjust the parent’s pointer.
2. 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.
3. 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

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); 
	} 
} 

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); 
}

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); 
}

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); 
}

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; 
}