using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        /*

        Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

        According to the definition of LCA on Wikipedia:

        “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants 

        (where we allow a node to be a descendant of itself).”

        */

        //This tree below is not a BST you moron

        Node a=new Node('a');

        Node b=new Node('b');

        Node c=new Node('c');

        Node d=new Node('d');

        Node e=new Node('e');

        Node f=new Node('f');

        a.left=b;

        a.right=c;

        b.left=d;

        b.right=e;

        c.right=f;

        Node ans=LowestCommonAncestor(a,b,f);

        Console.WriteLine(ans.val.ToString());

    }

    public class Node

    {

        public int val;

        public Node left,right;

        public Node(int value)

        {

            val=value;

            left=right=null;

        }

    }

    public static Node LowestCommonAncestor(Node root, Node p, Node q) {

        /*

        **FORGET THIS SOLUTION!!!

        ** Remember, this is a BINARY SERACH TREE. So, all values in left are ;less than any value in right.

        if(root==null || root==p|| root==q) return root;

        Node leftLCA=LowestCommonAncestor(root.left,p,q);

        Node rightLCA=LowestCommonAncestor(root.right,p,q);

        return leftLCA!=null && rightLCA!=null? root : leftLCA==null? rightLCA: leftLCA;

        */

        if(root==null||p==null || q==null ) return root;

        if(p.val>root.val && q.val>root.val) 

            return LowestCommonAncestor(root.right,p,q);

        else if (p.val<root.val && q.val<root.val)

            return LowestCommonAncestor(root.left,p,q);

        return root;

    }

}