Udemy: Master Coding Interview - Binary Search Tree - #128

Run Settings
LanguageC#
Language Version
Run Command
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); // } } }
Editor Settings
Theme
Key bindings
Full width
Lines