Binary Tree Implementation | C# Online Compiler

Binary Tree Implementation by Chandrika Iyer

using System;
using System.Text;
					
public class Program
{
	public static void Main()
	{
		BinarySearchTree bsT = new BinarySearchTree();

		bsT.Add(6);
		bsT.Add(7);
		bsT.Add(8);
		bsT.Add(12);
		bsT.Add(1);
		bsT.Add(15);
		
		Console.WriteLine("Min");
		Console.WriteLine(bsT.FindMin(bsT.root));
		Console.WriteLine();
		

		Console.WriteLine("Tree : ");
		bsT.PrintTree(bsT.root);


		Console.WriteLine("Deleting Node 6: ");
		bsT.Delete(bsT.root, 6);
		bsT.PrintTree(bsT.root);

		Console.WriteLine("Deleting Node 15: ");
		bsT.Delete(bsT.root, 15);
		bsT.PrintTree(bsT.root);

		Console.WriteLine("Deleting Node 1: ");
		bsT.Delete(bsT.root, 1);
		bsT.PrintTree(bsT.root);
		
		Console.WriteLine();
		Console.WriteLine("PreOrder");
		BinarySearchTree bsT1 = new BinarySearchTree();

		bsT1.Add(6);
		bsT1.Add(4);
		bsT1.Add(2);
		bsT1.Add(5);
		bsT1.Add(9);
		bsT1.Add(8);
		bsT1.Add(12);

		bsT1.PreOrderTraversal(bsT1.root);
		
		Console.WriteLine();
		Console.WriteLine("Inorder");
		bsT1.InOrderTraversal(bsT1.root);
		
		Console.WriteLine();
		Console.WriteLine("PostOrder");
		bsT.PostOrderTraversal(bsT.root);
		
		Console.WriteLine("FindKthMax: " + bsT1.FindKthMax(bsT1.root, 3));
		
		Console.WriteLine("Find ancestors");
		Console.WriteLine(bsT1.FindAncestors(bsT1.root, 12));
		
		
		Console.WriteLine("Find Height");
		Console.WriteLine(bsT1.FindHeight(bsT1.root));
		
		Console.WriteLine("FindKNodes");
		Console.WriteLine(bsT1.FindKNodes(bsT1.root, 2));
	}
}

public class Node
{
	public int Data { get; set; } 
	public Node Left { get; set; }
	public Node Right { get; set; }
	
	public Node(int data)
	{
		this.Data = data;
		this.Left = null;
		this.Right = null;
	}
	
}

public class BinarySearchTree
{
	public Node root { get; set; }
	
	public bool Add(int value)
	{
		this.root = Insert(root, value);
		return true;
	}
	
	public bool isEmpty()
	{
		return root == null;
	}
	
	public void PrintTree(Node current)
	{
		if(current == null)  return;
		Console.Write(current.Data + ", ");
		PrintTree(current.Left);
		PrintTree(current.Right);
	}
	
	public int FindMin(Node root)
	{
		if(root == null)
		{
			return -1;
		}
		
		if(root.Left == null)
		{
			return root.Data;
		}
		else
		{
			return FindMin(root.Left);
		}
	}
	
	public Node Insert(Node currentNode, int value)
	{
		if(currentNode == null)
		{
			return new Node(value);
		}
		
		if(value < currentNode.Data)
		{
			currentNode.Left = Insert(currentNode.Left, value);
		}
		else if (value > currentNode.Data)
		{
			currentNode.Right = Insert(currentNode.Right, value);
		}
		else
		{
			return currentNode;
		}
		
		return currentNode;
	}
	
	public  Node Search(int value)
	{
		if(isEmpty()) return null;
		Node currentNode = root;
		while(currentNode != null)
		{
			if(currentNode.Data == value)
			{
				return currentNode;
			}
			
			if(currentNode.Data < value)
			{
				currentNode = currentNode.Right;
			}
			else
			{
				currentNode = currentNode.Left;
			}
		}
		
		return null;
	}
	
	
	// Node is a leaf node
	// Node has a one child
	// Node has two children
	public bool Delete(Node currentNode, int value)
	{
		if(root == null)
		{
			return false;
		}
		
		// Store the parent of the current node
		Node parent = null;
		while(currentNode != null && currentNode.Data != value)
		{
			parent = currentNode;
			if(value < currentNode.Data)
			{
				currentNode = currentNode.Left;
			}
			else
			{
				currentNode = currentNode.Right;
			}
		}
		
		//Node not found
		if(currentNode == null)
		{
			return false;
		}
		// If the node to be deleted is  a leaf node
		else if (currentNode.Left == null && currentNode.Right == null)
		{
			//If the currentNode is also a root, i.e. only one node left
			if(currentNode.Data == root.Data)
			{
				root = null;
				return true;
			}
			//If the leaf node is to the left of its parent, then set the left child of the parent to null
			else if (currentNode.Data < parent.Data)
			{
				parent.Left = null;
				return true;
			}
			else if (currentNode.Data > parent.Data)
			{
				parent.Right = null;
				return true;
			}	
		}
		// If the node to be deleted has only left child
		else if (currentNode.Right == null)
		{
			//If the currentNode is also a root, set the root to the left child
			if(currentNode.Data == root.Data)
			{
				root = currentNode.Left;
				return true;
			}
			else if(parent.Data < currentNode.Data)
			{
				parent.Right = currentNode.Left;
				return true;
			}
			else if(parent.Data > currentNode.Data)
			{
				parent.Left = currentNode.Left;
				return true;
			}
		}
		// If the node to be deleted has only right child
		else if (currentNode.Left == null)
		{
			//If the currentNode is also a root, set the root to the right child
			if(currentNode.Data == root.Data)
			{
				root = currentNode.Right;
				return true;
			}
			else if (parent.Data < currentNode.Data)
			{
				parent.Right = currentNode.Right;
				return true;
			}
			else if (parent.Data > currentNode.Data)
			{
				parent.Left = currentNode.Right;
				return true;
			}
		}
		// If the node to be deleted has both children, find the smallest element of the right subtree and swap the values and delete the leaf
		else
		{
			Node leastNodeInRightSubTree = FindLeast(currentNode.Right);
			int temp = leastNodeInRightSubTree.Data;
			//Delete the leastNode
			Delete(root, temp);
			//Swap the leastnode value with current node
			currentNode.Data = temp;
			return true;
		}
		
		return false;
	}
	
	public void PreOrderTraversal(Node root)
	{
		if(root == null) return;
		Console.Write(root.Data + ", ");
		PreOrderTraversal(root.Left);
		PreOrderTraversal(root.Right);
	}
	
	public void InOrderTraversal(Node root)
	{
		if(root == null) return;
		InOrderTraversal(root.Left);
		Console.Write(root.Data + ", ");
		InOrderTraversal(root.Right);
	}
	
	
	public void PostOrderTraversal(Node root)
	{
		if(root == null) return;
		PostOrderTraversal(root.Left);
		PostOrderTraversal(root.Right);
		Console.Write(root.Data + ", ");
	}
	
	public StringBuilder InOrder(Node root, StringBuilder sb)
	{
		if(root == null)
		{
			return sb;
		}
		InOrder(root.Left, sb);
		sb.Append(root.Data).Append(",");
		InOrder(root.Right, sb);
		
		return sb;
	}
	
	public int FindKthMax(Node root, int k) {
		StringBuilder sb = InOrder(root, new StringBuilder());
		string[]  arr = sb.ToString().Split(',');
		if(arr.Length >= k)
		{
			return Int32.Parse(arr[arr.Length-k-1]);
		}
		
		return Int32.MinValue;
	}
	
	public String FindAncestors(Node root, int k)
	{
		StringBuilder sb = new StringBuilder();
		Node temp = root;
		while(temp != null && temp.Data != k)
		{
			sb.Append(temp.Data).Append(",");
			if(k < temp.Data)
			{
				temp = temp.Left;
			}
			else
			{
				temp = temp.Right;
			}
		}
		
		if(temp == null)
		{
			return String.Empty;
		}
		
		return sb.ToString();
	}
	
	public int FindHeight(Node root)
	{
		if(root == null) return -1;
		return 1 + Math.Max(FindHeight(root.Left), FindHeight(root.Right));
	}
	
	public String FindKNodes(Node root, int k) {
		return FindNodesR(root, k, new StringBuilder());
    }
	
	public int CountNodesInRange(Node n, int low, int high)
	{
		if(n == null)
		{
			return 0;
		}
		
		if(n.Data < low)
		{
			return CountNodesInRange(n.Right, low, high);
		}
		else if(n.Data > high)
		{
			return CountNodesInRange(n.Left, low, high);
		}
		
		return 1 + CountNodesInRange(n.Left, low, high) + CountNodesInRange(n.Right, low, high);
	}
	
	private String FindNodesR(Node root, int k, StringBuilder sb)
	{
		if(root == null) return null;
		if(k == 0)
		{
			sb.Append(root.Data).Append(",");
		}
		else
		{
			FindNodesR(root.Left, k-1, sb);
			FindNodesR(root.Right, k-1, sb);
		}
		
		return sb.ToString();
	}
	
	private Node FindLeast(Node currentNode)
	{
		Node temp = currentNode;
		while(temp.Left != null)
		{
			temp = temp.Left;
		}
		
		return temp;
	}
}

​x
 
using System;
using System.Text;
                    
public class Program
{
    public static void Main()
    {
        BinarySearchTree bsT = new BinarySearchTree();
​
        bsT.Add(6);
        bsT.Add(7);
        bsT.Add(8);
        bsT.Add(12);
        bsT.Add(1);
        bsT.Add(15);
        
        Console.WriteLine("Min");
        Console.WriteLine(bsT.FindMin(bsT.root));
        Console.WriteLine();
        
​
        Console.WriteLine("Tree : ");
        bsT.PrintTree(bsT.root);
​
​
        Console.WriteLine("Deleting Node 6: ");
        bsT.Delete(bsT.root, 6);
        bsT.PrintTree(bsT.root);
​
        Console.WriteLine("Deleting Node 15: ");
        bsT.Delete(bsT.root, 15);
        bsT.PrintTree(bsT.root);
​
        Console.WriteLine("Deleting Node 1: ");
        bsT.Delete(bsT.root, 1);
        bsT.PrintTree(bsT.root);
        
        Console.WriteLine();
        Console.WriteLine("PreOrder");
        BinarySearchTree bsT1 = new BinarySearchTree();
​
        bsT1.Add(6);
        bsT1.Add(4);
        bsT1.Add(2);
        bsT1.Add(5);
        bsT1.Add(9);
        bsT1.Add(8);
        bsT1.Add(12);
​
        bsT1.PreOrderTraversal(bsT1.root);
        
        Console.WriteLine();
        Console.WriteLine("Inorder");
        bsT1.InOrderTraversal(bsT1.root);
        
        Console.WriteLine();
        Console.WriteLine("PostOrder");
        bsT.PostOrderTraversal(bsT.root);
        
        Console.WriteLine("FindKthMax: " + bsT1.FindKthMax(bsT1.root, 3));
        
        Console.WriteLine("Find ancestors");
        Console.WriteLine(bsT1.FindAncestors(bsT1.root, 12));
        
        
        Console.WriteLine("Find Height");
        Console.WriteLine(bsT1.FindHeight(bsT1.root));
        
        Console.WriteLine("FindKNodes");
        Console.WriteLine(bsT1.FindKNodes(bsT1.root, 2));
    }
}
​
public class Node
{
    public int Data { get; set; } 
    public Node Left { get; set; }
    public Node Right { get; set; }
    
    public Node(int data)
    {
        this.Data = data;
        this.Left = null;
        this.Right = null;
    }
    
}
​
public class BinarySearchTree
{
    public Node root { get; set; }
    
    public bool Add(int value)
    {
        this.root = Insert(root, value);
        return true;
    }
    
    public bool isEmpty()
    {
        return root == null;
    }
    
    public void PrintTree(Node current)
    {
        if(current == null)  return;
        Console.Write(current.Data + ", ");
        PrintTree(current.Left);
        PrintTree(current.Right);
    }
    
    public int FindMin(Node root)
    {
        if(root == null)
        {
            return -1;
        }
        
        if(root.Left == null)
        {
            return root.Data;
        }
        else
        {
            return FindMin(root.Left);
        }
    }
    
    public Node Insert(Node currentNode, int value)
    {
        if(currentNode == null)
        {
            return new Node(value);
        }
        
        if(value < currentNode.Data)
        {
            currentNode.Left = Insert(currentNode.Left, value);
        }
        else if (value > currentNode.Data)
        {
            currentNode.Right = Insert(currentNode.Right, value);
        }
        else
        {
            return currentNode;
        }
        
        return currentNode;
    }
    
    public  Node Search(int value)
    {
        if(isEmpty()) return null;
        Node currentNode = root;
        while(currentNode != null)
        {
            if(currentNode.Data == value)
            {
                return currentNode;
            }
            
            if(currentNode.Data < value)
            {
                currentNode = currentNode.Right;
            }
            else
            {
                currentNode = currentNode.Left;
            }
        }
        
        return null;
    }
    
    
    // Node is a leaf node
    // Node has a one child
    // Node has two children
    public bool Delete(Node currentNode, int value)
    {
        if(root == null)
        {
            return false;
        }
        
        // Store the parent of the current node
        Node parent = null;
        while(currentNode != null && currentNode.Data != value)
        {
            parent = currentNode;
            if(value < currentNode.Data)
            {
                currentNode = currentNode.Left;
            }
            else
            {
                currentNode = currentNode.Right;
            }
        }
        
        //Node not found
        if(currentNode == null)
        {
            return false;
        }
        // If the node to be deleted is  a leaf node
        else if (currentNode.Left == null && currentNode.Right == null)
        {
            //If the currentNode is also a root, i.e. only one node left
            if(currentNode.Data == root.Data)
            {
                root = null;
                return true;
            }
            //If the leaf node is to the left of its parent, then set the left child of the parent to null
            else if (currentNode.Data < parent.Data)
            {
                parent.Left = null;
                return true;
            }
            else if (currentNode.Data > parent.Data)
            {
                parent.Right = null;
                return true;
            }   
        }
        // If the node to be deleted has only left child
        else if (currentNode.Right == null)
        {
            //If the currentNode is also a root, set the root to the left child
            if(currentNode.Data == root.Data)
            {
                root = currentNode.Left;
                return true;
            }
            else if(parent.Data < currentNode.Data)
            {
                parent.Right = currentNode.Left;
                return true;
            }
            else if(parent.Data > currentNode.Data)
            {
                parent.Left = currentNode.Left;
                return true;
            }
        }
        // If the node to be deleted has only right child
        else if (currentNode.Left == null)
        {
            //If the currentNode is also a root, set the root to the right child
            if(currentNode.Data == root.Data)
            {
                root = currentNode.Right;
                return true;
            }
            else if (parent.Data < currentNode.Data)
            {
                parent.Right = currentNode.Right;
                return true;
            }
            else if (parent.Data > currentNode.Data)
            {
                parent.Left = currentNode.Right;
                return true;
            }
        }
        // If the node to be deleted has both children, find the smallest element of the right subtree and swap the values and delete the leaf
        else
        {
            Node leastNodeInRightSubTree = FindLeast(currentNode.Right);
            int temp = leastNodeInRightSubTree.Data;
            //Delete the leastNode
            Delete(root, temp);
            //Swap the leastnode value with current node
            currentNode.Data = temp;
            return true;
        }
        
        return false;
    }
    
    public void PreOrderTraversal(Node root)
    {
        if(root == null) return;
        Console.Write(root.Data + ", ");
        PreOrderTraversal(root.Left);
        PreOrderTraversal(root.Right);
    }
    
    public void InOrderTraversal(Node root)
    {
        if(root == null) return;
        InOrderTraversal(root.Left);
        Console.Write(root.Data + ", ");
        InOrderTraversal(root.Right);
    }
    
    
    public void PostOrderTraversal(Node root)
    {
        if(root == null) return;
        PostOrderTraversal(root.Left);
        PostOrderTraversal(root.Right);
        Console.Write(root.Data + ", ");
    }
    
    public StringBuilder InOrder(Node root, StringBuilder sb)
    {
        if(root == null)
        {
            return sb;
        }
        InOrder(root.Left, sb);
        sb.Append(root.Data).Append(",");
        InOrder(root.Right, sb);
        
        return sb;
    }
    
    public int FindKthMax(Node root, int k) {
        StringBuilder sb = InOrder(root, new StringBuilder());
        string[]  arr = sb.ToString().Split(',');
        if(arr.Length >= k)
        {
            return Int32.Parse(arr[arr.Length-k-1]);
        }
        
        return Int32.MinValue;
    }
    
    public String FindAncestors(Node root, int k)
    {
        StringBuilder sb = new StringBuilder();
        Node temp = root;
        while(temp != null && temp.Data != k)
        {
            sb.Append(temp.Data).Append(",");
            if(k < temp.Data)
            {
                temp = temp.Left;
            }
            else
            {
                temp = temp.Right;
            }
        }
        
        if(temp == null)
        {
            return String.Empty;
        }
        
        return sb.ToString();
    }
    
    public int FindHeight(Node root)
    {
        if(root == null) return -1;
        return 1 + Math.Max(FindHeight(root.Left), FindHeight(root.Right));
    }
    
    public String FindKNodes(Node root, int k) {
        return FindNodesR(root, k, new StringBuilder());
    }
    
    public int CountNodesInRange(Node n, int low, int high)
    {
        if(n == null)
        {
            return 0;
        }
        
        if(n.Data < low)
        {
            return CountNodesInRange(n.Right, low, high);
        }
        else if(n.Data > high)
        {
            return CountNodesInRange(n.Left, low, high);
        }
        
        return 1 + CountNodesInRange(n.Left, low, high) + CountNodesInRange(n.Right, low, high);
    }
    
    private String FindNodesR(Node root, int k, StringBuilder sb)
    {
        if(root == null) return null;
        if(k == 0)
        {
            sb.Append(root.Data).Append(",");
        }
        else
        {
            FindNodesR(root.Left, k-1, sb);
            FindNodesR(root.Right, k-1, sb);
        }
        
        return sb.ToString();
    }
    
    private Node FindLeast(Node currentNode)
    {
        Node temp = currentNode;
        while(temp.Left != null)
        {
            temp = temp.Left;
        }
        
        return temp;
    }
}

User Name or Email

Last Run:	7:54:35 am
Compile:	0.189s
Execute:	0s
Memory:	32kb
CPU:	0s

View IL Code