Utils.cs - Binary Trees

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

namespace BinaryTree
{
    class Utils
    {

        public static void printInOrderTabs<T>(BinNode<T> node, String tabs = "")
        {
            if (node == null)
                return;

            printInOrderTabs(node.GetLeft(), tabs + "\t");
            Console.WriteLine(tabs + node.ToString());
            printInOrderTabs(node.GetRight(), tabs + "\t");
        }

        public static void printPreOrder<T>(BinNode<T> node)
        {
            if (node == null)
                return;

            Console.Write(node.GetValue().ToString() + ", ");
            printPreOrder(node.GetLeft());
            printPreOrder(node.GetRight());
        }

        public static void printInOrder<T>(BinNode<T> node)
        {
            if (node == null)
                return;

            printInOrder(node.GetLeft());
            Console.Write(node.GetValue().ToString() + ", ");
            printInOrder(node.GetRight());
        }

        public static void printPostOrder<T>(BinNode<T> node)
        {
            if (node == null)
                return;

            printInOrder(node.GetLeft());
            printInOrder(node.GetRight());
            Console.Write(node.GetValue().ToString() + ", ");
        }

        static readonly int MAX_VALUE = 100;

        public static BinNode<int> createRandomTree(int points)
        {
            if (points <= 0)
                return null;

            Random rand = new Random();

            Func<BinNode<int>> randNode = () => new BinNode<int>(rand.Next(MAX_VALUE));
            Func<bool> randBool = () => rand.Next(2) == 1;

            BinNode<int> head = randNode();


            for (int i = 0; i < points - 1; i++)
            {
                BinNode<int> curr = head;

                while (curr.HasLeft() && curr.HasRight())
                {
                    if (randBool())
                        curr = curr.GetLeft();
                    else
                        curr = curr.GetRight();
                }

                if (curr.HasLeft())
                    curr.SetRight(randNode());
                else if (curr.HasRight())
                    curr.SetLeft(randNode());
                else
                {
                    if (randBool())
                        curr.SetLeft(randNode());
                    else
                        curr.SetRight(randNode());
                }

            }

            return head;
        }

        public static BinNode<int> createTree(int[] array)
        {
            if (array.Length == 0)
                return null;

            BinNode<int> tree = new BinNode<int>(array[0]);

            for (int i = 1; i < array.Length; i++)
                insertIntoTree(tree, array[i]);

            return tree;
        }

        public static void insertIntoTree(BinNode<int> tree, int val)
        {
            if (tree == null || tree.GetValue() == val)
                return;

            if (tree.GetValue() > val)
            {
                if (tree.HasLeft())
                    insertIntoTree(tree.GetLeft(), val);
                else
                    tree.SetLeft(new BinNode<int>(val));
            }

            if (tree.GetValue() < val)
            {
                if (tree.HasRight())
                    insertIntoTree(tree.GetRight(), val);
                else
                    tree.SetRight(new BinNode<int>(val));
            }
        }

        public static BinNode<int> getTree(int[] preorder, int[] inorder,
                    int startPreorder = -2, int startInorder = -2, int length = -1)
        {
            // exit condition
            if (startInorder >= inorder.Length || startPreorder >= inorder.Length || inorder.Length != preorder.Length)
                return null;

            // default value change
            if (length == -1)
            {
                length = inorder.Length;
                startInorder = 0;
                startPreorder = 0;
            }

            int currentVal = preorder[startPreorder];

            int valIndex = -1;

            for (int i = startInorder; i < startInorder + length; i++)
            {
                if (inorder[i].Equals(currentVal))
                {
                    valIndex = i;
                    break;
                }
            }

            if (valIndex == -1)
                return null;

            int leftLength = valIndex - startInorder;
            int rightLength = length - leftLength - 1;

            BinNode<int> node = new BinNode<int>(currentVal);
            node.SetLeft(getTree(preorder, inorder, startPreorder + 1, startInorder, leftLength));
            node.SetRight(getTree(preorder, inorder, startPreorder + 1 + leftLength, valIndex + 1, rightLength));

            return node;
        }

        public static void printByLines<T>(BinNode<T> tree)
        {
            if (tree == null)
                return;

            List<BinNode<T>> curr = new List<BinNode<T>>();
            curr.Add(tree);
            List<BinNode<T>> next = new List<BinNode<T>>();

            while (curr.Count > 0)
            {
                foreach (BinNode<T> node in curr)
                {
                    if (node.HasLeft())
                        next.Add(node.GetLeft());
                    if (node.HasRight())
                        next.Add(node.GetRight());

                    Console.Write(node + ", ");
                }

                Console.WriteLine();

                curr.Clear();
                curr.AddRange(next);
                next.Clear();
            }
        }

        public static int treeHeight<T>(BinNode<T> node)
        {
            if (node == null)
                return 0;

            int height = 1;

            height += Math.Max(treeHeight(node.GetLeft()), treeHeight(node.GetRight()));

            return height;
        }

        public static void printHeight<T>(BinNode<T> node, int n)
        {
            if (node == null)
                return;

            if (n == 0)
                Console.Write(node.ToString() + ", ");
            else
            {
                printHeight(node.GetLeft(), n - 1);
                printHeight(node.GetRight(), n - 1);
            }
        }

        public static int sumRightChildren(BinNode<int> node)
        {
            if (node == null)
                return 0;

            return sumRightChildren(node.GetLeft()) + sumRightChildren(node.GetRight())
                + (node.HasRight() ? node.GetRight().GetValue() : 0);
        }

        /// <summary>
        /// gets in a node
        /// sums the lone right children.
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public static int sumRightLoneChildren(BinNode<int> node)
        {
            if (node == null)
                return 0;

            int sum = 0;

            // if the right is the only child
            if (!node.HasLeft() && node.HasRight())
                sum += node.GetRight().GetValue();

            sum += sumRightLoneChildren(node.GetLeft()) + sumRightLoneChildren(node.GetRight());

            return sum;
        }

        /// <summary>
        /// gets in a node
        /// returns the sum of the lone children
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public static int sumLoneChildren(BinNode<int> node)
        {
            if (node == null)
                return 0;

            int sum = 0;

            if (node.HasRight() && !node.HasLeft())
                sum += node.GetRight().GetValue();
            else if (!node.HasRight() && node.HasLeft())
                sum += node.GetLeft().GetValue();

            sum += sumLoneChildren(node.GetLeft()) + sumLoneChildren(node.GetRight());
            return sum;
        }

        /// <summary>
        /// gets in a node
        /// returns a sum of parents with single children
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public static int sumParentsWithSingleChild(BinNode<int> node)
        {
            if (node == null)
                return 0;

            int sum = 0;
            if (node.HasRight() ^ node.HasLeft())
                sum += node.GetValue();

            return sum + sumParentsWithSingleChild(node.GetLeft()) + sumParentsWithSingleChild(node.GetRight());
        }

        public static bool isParent<T>(BinNode<T> node)
        {
            if (node == null)
                return false;

            return node.HasRight() || node.HasLeft();
        }

        public static bool isGrandparent<T>(BinNode<T> node)
        {
            if (node == null)
                return false;

            return isParent(node.GetRight()) || isParent(node.GetLeft());
        }

        public static int sumGrandparents(BinNode<int> node)
        {
            if (!isGrandparent(node))
                return 0;

            return sumGrandparents(node.GetLeft()) + sumGrandparents(node.GetRight())
                + node.GetValue();
        }

        public static int sumDividedBy3(BinNode<int> node)
        {
            if (node == null)
                return 0;

            return (node.GetValue() % 3 == 0 ? node.GetValue() : 0) + sumDividedBy3(node.GetLeft()) + sumDividedBy3(node.GetRight());
        }

        public static int sumValuesLowerThan(BinNode<int> node, int max)
        {
            if (node == null)
                return 0;

            return (node.GetValue() < max ? node.GetValue() : 0) + sumValuesLowerThan(node.GetLeft(), max) + sumValuesLowerThan(node.GetRight(), max);
        }

        private static int sumDigits(int num)
        {
            int sum = 0;

            while (num != 0)
            {
                sum += num % 10;
                num /= 10;
            }

            return sum;
        }

        public static int sumOddDigitSums(BinNode<int> node)
        {
            if (node == null)
                return 0;

            return (sumDigits(node.GetValue()) % 2 == 1 ? node.GetValue() : 0) + sumOddDigitSums(node.GetLeft()) + sumOddDigitSums(node.GetRight());
        }

        // im different

        public static int sumChildrenDoubleTheirParents(BinNode<int> node)
        {
            if (node == null)
                return 0;

            int doublethestakesdoublethewin = node.GetValue() * 2;
            int sum = 0;

            if (node.HasRight() && node.GetRight().GetValue() >= doublethestakesdoublethewin)
                sum += node.GetRight().GetValue();

            if (node.HasLeft() && node.GetLeft().GetValue() >= 2 * doublethestakesdoublethewin)
                sum += node.GetLeft().GetValue();

            return sum + sumChildrenDoubleTheirParents(node.GetLeft()) + sumChildrenDoubleTheirParents(node.GetRight());
        }

        public static int sumStronkerBrothers(BinNode<int> node)
        {
            if (node == null)
                return 0;

            int sum = 0;

            if (node.HasLeft() && node.HasRight() && node.GetRight().GetValue() != node.GetLeft().GetValue())
            {
                if (node.GetRight().GetValue() > node.GetLeft().GetValue())
                    sum += node.GetRight().GetValue();
                else
                    sum += node.GetLeft().GetValue();
            }

            return sum + sumStronkerBrothers(node.GetLeft()) + sumStronkerBrothers(node.GetRight());
        }

        public static void doLines<T>(BinNode<T> node, Func<BinNode<T>, bool> action)
        {
            if (node == null)
                return;

            Queue<BinNode<T>> q = new Queue<BinNode<T>>();
            q.Insert(node);

            while (!q.isEmpty())
            {
                BinNode<T> curr = q.remove();

                if (action(curr))
                    break;

                if (curr.HasLeft())
                    q.Insert(curr.GetLeft());
                if (curr.HasRight())
                    q.Insert(curr.GetRight());
            }
        }

        public static void printEvenNumsByLines(BinNode<int> node)
        {
            doLines(node, x =>
            {
                if (x.GetValue() % 2 == 0)
                    Console.WriteLine(x.GetValue());
                return false;
            });
        }

        public static void printParentWithSingleChild<T>(BinNode<T> node)
        {
            doLines(node, x =>
            {
                if (node.HasRight() ^ node.HasLeft())
                    Console.WriteLine(node.ToString());
                return false;
            });
        }

        public static void printParentSumChildrenGreater(BinNode<int> node)
        {
            doLines(node, x =>
            {
                int sum = 0;
                sum += node.HasLeft() ? node.GetLeft().GetValue() : 0;
                sum += node.HasRight() ? node.GetRight().GetValue() : 0;
                if (sum > node.GetValue())
                    Console.WriteLine(node.ToString());
                return false;
            });
        }

        public static bool areTreesSimiliar<T>(BinNode<T> tree1, BinNode<T> tree2)
        {
            if (tree1 == null || tree2 == null)
                return tree1 == null && tree2 == null;

            bool sameVals;

            if (tree1.GetValue() == null && tree2.GetValue() == null)
                sameVals = true;
            else if (tree1.GetValue() != null)
                sameVals = tree1.GetValue().Equals(tree2.GetValue());
            else
                sameVals = false;

            return sameVals && areTreesSimiliar(tree1.GetLeft(), tree2.GetLeft()) && areTreesSimiliar(tree1.GetRight(), tree2.GetRight());
        }



    }

}