using System;
using System.Collections.Generic;
using System.Linq;
class MainClass {
static void Main() {
Console.WriteLine("Hello World!");
BST tree = new BST();
tree.Insert(9);
tree.Insert(4);
tree.Insert(6);
tree.Insert(20);
tree.Insert(170);
tree.Insert(15);
tree.Insert(1);
tree.DepthFirstSearchInOrder();
tree.DepthFirstSearchPreOrder();
tree.DepthFirstSearchPostOrder();
}
}
public class BST
{
public BST()
{
Root = null;
}
public Node Root { get; set; }
public void PrettyPrint()
{
PrettyPrint(Root);
}
public void DepthFirstSearchInOrder()
{
List<int> output = new List<int>();
Console.WriteLine(String.Join(",", DepthFirstSearchInOrder(Root, output)));
}
public void DepthFirstSearchPreOrder()
{
List<int> output = new List<int>();
Console.WriteLine(String.Join(",", DepthFirstSearchPreOrder(Root, output)));
}
public void DepthFirstSearchPostOrder()
{
List<int> output = new List<int>();
Console.WriteLine(String.Join(",", DepthFirstSearchPostOrder(Root, output)));
}
public List<int> DepthFirstSearchInOrder(Node node, List<int> output)
{
if(node.Left != null)
DepthFirstSearchInOrder(node.Left, output);
output.Add(node.Value);
if(node.Right != null)
DepthFirstSearchInOrder(node.Right, output);
return output;
}
public List<int> DepthFirstSearchPreOrder(Node node, List<int> output)
{
output.Add(node.Value);
if(node.Left != null)
DepthFirstSearchPreOrder(node.Left, output);
if(node.Right != null)
DepthFirstSearchPreOrder(node.Right, output);
return output;
}
public List<int> DepthFirstSearchPostOrder(Node node, List<int> output)
{
if(node.Left != null)
DepthFirstSearchPostOrder(node.Left, output);
if(node.Right != null)
DepthFirstSearchPostOrder(node.Right, output);
output.Add(node.Value);
return output;
}
public void BreadthFirstSearch()
{
List<int> output = new List<int>();
Node currentNode = Root;
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(currentNode);
while(queue.Count() > 0)
{
currentNode = queue.Dequeue();
output.Add(currentNode.Value);
if(currentNode.Left != null)
queue.Enqueue(currentNode.Left);
if(currentNode.Right != null)
queue.Enqueue(currentNode.Right);
}
Console.WriteLine($"BFS Output: {String.Join(",", output)}");
}
public void PrettyPrint(Node root)
{
if(root == null)
return;
else
{
Console.WriteLine(root.Value);
PrettyPrint(root.Left);
PrettyPrint(root.Right);
}
}
public void Insert(int value)
{
Node newNode = new Node(value);
if(Root == null)
Root = newNode;
else
{
var currentNode = Root;
while (currentNode != null)
{
if(currentNode.Left == null && value < currentNode.Value)
{
currentNode.Left = newNode;
return;
}
else if(currentNode.Right == null && value > currentNode.Value)
{
currentNode.Right = newNode;
return;
}
if(value < currentNode.Value)
currentNode = currentNode.Left;
else
currentNode = currentNode.Right;
}
}
}
}
public class Node
{
public Node(int value)
{
Left = null;
Right = null;
Value = value;
}
public Node Left { get; set; }
public Node Right { get; set; }
public int Value { get; set; }
}
