Udemy: Master Coding Interview - Depth First Search - #201
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297
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()));
}
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;
}
}
Csharp
INFO