using System;
using System.Collections.Generic;
public class Node {
public Node left = null;
public Node right = null;
public int value = 0;
public Node(int value) {
this.value = value;
}
}
class BinarySearchTree {
public Node root = null;
static void Main() {
Console.WriteLine("Hello World!");
BinarySearchTree bst = new BinarySearchTree();
Console.WriteLine("bst = " + bst.ToString());
bst.Insert(9);
bst.Insert(4);
bst.Insert(1);
bst.Insert(6);
bst.Insert(20);
bst.Insert(15);
bst.Insert(170);
Console.WriteLine("bst = " + bst.ToString());
bst.BreadthFirstSearch();
bst.BreadthFirstSearchRecursive();
Console.WriteLine("DFS In Order: " + bst.ToString(bst.DFSInOrder()));
Console.WriteLine("DFS Pre Order: " + bst.ToString(bst.DFSPreOrder()));
Console.WriteLine("DFS Post Order: " + bst.ToString(bst.DFSPostOrder()));
if (bst.IsValid()) {
Console.WriteLine("BST Validated!");
} else {
Console.WriteLine("BST NOT Valid!");
}
}
public BinarySearchTree() {
}
public string ToString() {
string s = "{";
if (this.root != null) {
s += NodeToString(this.root);
}
s += "}";
return s;
}
public string NodeToString(Node n) {
string s = "" + n.value;
if (n.left != null || n.right != null) {
s += "(";
}
if (n.left != null) {
s += NodeToString(n.left);
}
if (n.left != null || n.right != null) {
s += ",";
}
if (n.right != null) {
s += NodeToString(n.right);
}
if (n.left != null || n.right != null) {
s += ")";
}
return s;
}
public void Insert(int value) {
Node item = new Node(value);
if (this.root == null) {
this.root = item;
} else {
InsertAsChild(this.root, item);
}
}
public void InsertAsChild(Node parent, Node child) {
if (child.value < parent.value) {
if (parent.left == null) {
parent.left = child;
} else {
InsertAsChild(parent.left, child);
}
} else if (child.value > parent.value) {
if (parent.right == null) {
parent.right = child;
} else {
InsertAsChild(parent.right, child);
}
}
}
public Node Lookup(int value) {
if (this.root != null) {
return LookupChild(this.root, value);
}
return null;
}
public Node LookupChild(Node parent, int value) {
if (parent == null || parent.value == value) {
return parent;
}
if (value < parent.value) {
return LookupChild(parent.left, value);
}
if (value > parent.value) {
return LookupChild(parent.right, value);
}
return null;
}
public void Remove(int value) {
if (this.root != null) {
Node current = this.root;
Node prev = null;
bool wasPrevLeft = false;
Node found = null;
while (current != null) {
if (found != null) {
if (current.left != null) {
if (wasPrevLeft) {
prev.left = current.left;
} else {
prev.right = current.left;
}
current.left.left = found.left;
current.left.right = found.right;
current.left = null;
return;
} else {
if (wasPrevLeft) {
prev.left = current;
} else {
prev.right = current;
}
current.left = found.left;
return;
}
} else if (value == current.value) {
found = current;
if (found.right == null) {
if (wasPrevLeft) {
prev.left = found.left;
} else {
prev.right = found.left;
}
return;
} else if (found.left == null) {
if (wasPrevLeft) {
prev.left = found.right;
} else {
prev.right = found.right;
}
return;
} else {
current = current.right;
}
} else if (value < current.value) {
prev = current;
wasPrevLeft = true;
current = current.left;
} else if (value > current.value) {
prev = current;
wasPrevLeft = false;
current = current.right;
}
}
}
}
public void RemoveChild(Node parent, int value) {
// if (parent.left != null) {
// if (parent.left.value == value) {
// this.root = null;
// } else {
// RemoveChild(this.root, value);
// }
// }
// if (parent.value == value) {
// }
// if (value < parent.value) {
// return LookupChild(parent.left, value);
// }
// if (value > parent.value) {
// return LookupChild(parent.right, value);
// }
}
public void BreadthFirstSearch(/*int value*/) {
Node current = this.root;
List<int> list = new List<int> ();
Queue<Node> queue = new Queue<Node> ();
queue.Enqueue(current);
while (queue.Count > 0) {
current = queue.Dequeue();
list.Add(current.value);
if (current.left != null) {
queue.Enqueue(current.left);
}
if (current.right != null) {
queue.Enqueue(current.right);
}
}
Console.WriteLine("BFS: " + ToString(list));
}
public void BreadthFirstSearchRecursive(/*int value*/) {
Node current = this.root;
List<int> list = new List<int> ();
Queue<Node> queue = new Queue<Node> ();
queue.Enqueue(current);
list = BFSR(queue, list);
Console.WriteLine("BFS Recursive: " + ToString(list));
}
public string ToString(List<int> list) {
string s = "{";
int count = 0;
foreach (int v in list) {
if (count > 0) {
s += ", ";
}
s += "" + v;
count++;
}
s += "}";
return s;
}
public List<int> BFSR(Queue<Node> queue, List<int> list) {
if (queue.Count == 0) {
return list;
}
Node current = queue.Dequeue();
list.Add(current.value);
if (current.left != null) {
queue.Enqueue(current.left);
}
if (current.right != null) {
queue.Enqueue(current.right);
}
return BFSR(queue, list);
}
public List<int> DFSInOrder() {
List<int> list = new List<int> ();
return TraverseInOrder(this.root, list);
}
public List<int> DFSPostOrder() {
List<int> list = new List<int> ();
return TraversePostOrder(this.root, list);
}
public List<int> DFSPreOrder() {
List<int> list = new List<int> ();
return TraversePreOrder(this.root, list);
}
public List<int> TraverseInOrder(Node node, List<int> list) {
if (node.left != null) {
TraverseInOrder(node.left, list);
}
list.Add(node.value);
if (node.right != null) {
TraverseInOrder(node.right, list);
}
return list;
}
public List<int> TraversePreOrder(Node node, List<int> list) {
list.Add(node.value);
if (node.left != null) {
TraversePreOrder(node.left, list);
}
if (node.right != null) {
TraversePreOrder(node.right, list);
}
return list;
}
public List<int> TraversePostOrder(Node node, List<int> list) {
if (node.left != null) {
TraversePostOrder(node.left, list);
}
if (node.right != null) {
TraversePostOrder(node.right, list);
}
list.Add(node.value);
return list;
}
public bool IsValid() {
Node current = this.root;
Queue<Node> queue = new Queue<Node> ();
queue.Enqueue(this.root);
while (queue.Count > 0) {
current = queue.Dequeue();
if (current.left != null) {
queue.Enqueue(current.left);
if (current.left.value >= current.value) {
return false;
}
}
if (current.right != null) {
queue.Enqueue(current.right);
if (current.right.value <= current.value) {
return false;
}
}
}
return true;
}
}