Udemy: Master Coding Interview - Binary Search Tree - #128
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195
using System;
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(60);
bst.Insert(30);
bst.Insert(72);
bst.Insert(14);
bst.Insert(1);
bst.Insert(51);
bst.Insert(38);
bst.Insert(55);
bst.Insert(54);
bst.Insert(38);
bst.Insert(44);
Console.WriteLine("bst = " + bst.ToString());
bst.Remove(51);
Console.WriteLine("bst = " + bst.ToString());
bst.Remove(14);
Console.WriteLine("bst = " + bst.ToString());
bst.Remove(30);
Console.WriteLine("bst = " + bst.ToString());
}
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);
// }
}
}
Csharp
INFO