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

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);
        // }
    }
}