BST

BST

using System;
using System.Collections.Generic;

namespace BST
{
    public class Program
    {
        public static void Main(string[] args)
        {
            // BST checker
            Node n1 = new Node(16);
            Node n2 = new Node(11);
            Node n3 = new Node(18);
            Node n4 = new Node(17);
            Node n5 = new Node(19);
            
            n1.Left = n2;
            n2.Right = n5;
            n1.Right = n3;
            n3.Left = n4;
            
            Console.WriteLine("Is n1 a BST? {0}", isBST(n1));
            
            // BST display
            Console.WriteLine("BST display:");
            BST bst = new BST();
            bst.Add(4);
            bst.Add(1);
            bst.Add(5);
            bst.Add(7);
            bst.Add(3);
            bst.DisplayInSortedOrder();
            
            Console.WriteLine("Second largest element is {0}", bst.getSecondLargestElement());
            
            bst.Remove(3);
            bst.DisplayInSortedOrder();
            
            bst.Remove(4);
            bst.DisplayInSortedOrder();
            
            Console.WriteLine("Second largest element is {0}", bst.getSecondLargestElement());
            
            bst.Add(9);
            bst.DisplayInSortedOrder();
            
            Console.WriteLine("Second largest element is {0}", bst.getSecondLargestElement());
        }
        
        private static bool isBST(Node n) {
            return isBST(n, Int32.MinValue, Int32.MaxValue);
        }
        
        private static bool isBST(Node n, int min, int max) {
            if (n == null) {
                return true;
            }
            
            if (n.Data < min || n.Data > max) {
                return false;
            }
            
            return isBST(n.Left, min, n.Data) && isBST(n.Right, n.Data, max);
        }
    }
    
    class Node {
        public Node(int data) {
            this.Data = data;
        }
        
        public int Data {get; set;}
        
        public Node Left {get; set;}
        
        public Node Right {get; set;}
       
    }
    
    class BST {
    
        private Node root;
      
        public void Add(int value) {
            root = add(root, value);
        }
        
        private Node add(Node n, int value) {
            if (n == null) {
                n = new Node(value);
            } else {
                if (value <= n.Data) {
                    n.Left = add(n.Left, value);
                } else {
                    n.Right = add(n.Right, value);
                }
            }
            
            return n;
        }
        
        public Node Get(int value) {
            return get(root, value);
        }
        
        private Node get(Node n, int value) {
            if (n == null) {
                return null;
            }
            
            if (value == n.Data) {
                return n;
            } 
            
            return (value <= n.Data) ? get(n.Left, value) : get(n.Right, value);
        }
        
        private Node remove(Node n, int value) {
            if (n == null) {
                return null;
            }
            
            if (n.Data == value) {
                
                if (n.Left == null && n.Right == null) {
                    return null;
                } else if (n.Left != null && n.Right != null) {
                    n.Data = getMinValueFromSubtree(n.Right);
                    n.Right = remove(n.Right, n.Data);
                } else if (n.Left != null) {
                    return n.Left;
                } else if (n.Right != null) {
                    return n.Right;
                }
                
            } else if (n.Data < value) {
                n.Right = remove(n.Right, value);
            } else if (n.Data > value) {
                n.Left = remove(n.Left, value);
            }
            
            return n;
        }
        
        private int getMinValueFromSubtree(Node n) {
            if (n.Left == null) {
                return n.Data;
            }
            
            return getMinValueFromSubtree(n.Left);
        }
        
        public void Remove(int value) {
            root = remove(root, value);
        }
        
        private void traverseInOrder(Node n, List<int>output) {
            if (n == null) {
                return;
            }
            
            traverseInOrder(n.Left, output);
            output.Add(n.Data);
            traverseInOrder(n.Right, output);
        }
       
        public List<int> GetSortedList() {
            var sortedOutput = new List<int>();
            traverseInOrder(root, sortedOutput);
            return sortedOutput;
        }
        
        public void DisplayInSortedOrder() {
            
            var sortedOutput = GetSortedList();
          
            foreach(int item in sortedOutput) {
                Console.Write(item + " ");
            }
    
            Console.WriteLine();
        }
        
        public int getSecondLargestElement() {
           if (root.Right == null) {
               return getMaxValue(root.Left);
           }
           
           Node prev = root;
           
           Node current = root.Right;
           
           while (current.Right != null) {
               prev = current;
               current = current.Right;
           }
           
           if (current.Left != null) {
               return getMaxValue(current.Left);
           }
           
           return prev.Data;
        }
        
        int getMaxValue(Node n) {
            if (n.Right == null) {
                return n.Data;
            }
            
            return getMaxValue(n.Right);
        }
        
    }
}