Udemy: Master Coding Interview - Validate BST - #202

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