Udemy: Master Coding Interview - Depth First Search - #201

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