Lunedi quiz #1 - soluzione

    class Node
    {
        public Node Left {get; private set;}
        public Node Right { get; private set; }
        public string Value { get; private set; }

        public Node(Node left, Node right, string value)
        {
            this.Left = left;
            this.Right = right;
            this.Value = value;
        }

        // l'idea: naviga l'albero e se il primo nodo è sul lato opposto del secondo
        // rispetto a root, allora i percorsi divergono, quindi root è l'antenato cercato
        //
        // se sono tutti e due a sinistra, scendi ricorsivamente sul nodo sinistro di root
        // altrimenti scendi ricorsivamente sul nodo destro
        public static Node FindCommonAncestor(Node root, Node first, Node second)
        {
            if (root == null)
            {
                throw new Exception("Cannot find a path from root to children");
            }

            if ((root == first) || (root == second))
            {
                VerifyPathExists(root, first);
                VerifyPathExists(root, second);
                return root;
            }

            if ((root.Value == first.Value) || (root.Value == second.Value))
            {
                throw new Exception("Duplicate value found");
            }

            var comp1 = string.Compare(root.Value, first.Value);
            var comp2 = string.Compare(root.Value, second.Value);

            // i percorsi divergono, root è l'antenato cercato
            if ((comp1 * comp2) < 0)
            {
                VerifyPathExists(root, first);
                VerifyPathExists(root, second);

                return root;
            }

            if (comp1 > 0)
            {
                // sia first che second sono a sinistra

                return FindCommonAncestor(root.Left, first, second);
            }
            else
            {
                return FindCommonAncestor(root.Right, first, second);
            }
        }

        private static void VerifyPathExists(Node root, Node child)
        {
            if (root == null)
            {
                throw new Exception("Cannot find a path from root to children");
            }

            if (root == child)
            {
                return;
            }

            if (root.Value == child.Value)
            {
                throw new Exception("Duplicate value found");
            }

            if (string.Compare(root.Value, child.Value) < 0)
            {
                VerifyPathExists(root.Right, child);
            }
            else
            {
                VerifyPathExists(root.Left, child);
            }
        }
    }