using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Assessment3Part1
{
    public class BinaryNode
    {
        public int value;
        public BinaryNode left;
        public BinaryNode right;

        public BinaryNode (int value)
        {
            this.value = value;

            left = null;
            right = null;
        }
    }


    public class BinaryGraph
    {
        private BinaryNode root;
        public BinaryGraph()
        {
            root = null;
        }
        public void Insert(int value)
        {
            root = InsertCheck(root, value);
        }

        private BinaryNode InsertCheck(BinaryNode node, int value)
        {
            if (node == null)
            {
                node = new BinaryNode(value);
            }
            else if(value < node.value)
            {
                node.left = InsertCheck(node.left, value);
            }
            else
            {
                node.right = InsertCheck(node.right, value);
            }
            return node;
        }
        public void TraverseInOrder()
        {
            InOrderHelper(root);
            Console.WriteLine();
        }

        private void InOrderHelper(BinaryNode node)
        {
            if (node != null)
            {
                InOrderHelper(node.left);
                Console.Write(node.value + " ");
                InOrderHelper(node.right);
            }
        }
        public void TraversePreOrder()
        {
            PreOrderHelper(root);
            Console.WriteLine();
        }

        private void PreOrderHelper(BinaryNode node)
        {
            if (node != null)
            {
                Console.Write(node.value + " ");
                PreOrderHelper(node.left);
                PreOrderHelper(node.right);
            }
        }

        public bool Contains(int value)
        {
            return ContainsHelper(root, value);
        }

        private bool ContainsHelper(BinaryNode node, int value)
        {
            if (node == null)
            {
                return false;
            }
            else if (node.value == value)
            {
                return true;
            }
            else if (value < node.value)
            {
                return ContainsHelper(node.left, value);
            }
            else
            {
                return ContainsHelper(node.right, value);
            }
        }
    }
}