CareerCup

Assuming there aren't duplicate values or the two integers provided don't repeat,

Carry out a DFS over the tree, and
- when you find the one of the two values, store the stack.
- continue the DFS search
- when you find the next value, store the stack.
- terminate the search.
- Reverse the two stacks
- keep popping both the stacks until both of them have identical nodes.
- stop when the nodes in the stack differ.

The recent most popped node or nil is the answer.

// ZoomBA uLanguage. Simple.
paths = [ '', '' ]
def find_paths( key1, key2,  node , path  ){
  if ( !empty(path.0) && !empty(path.1) ) return 
  if ( node == null ) {
    if ( path #$ key1 ){ paths.0 = path }
    if ( path #$ key2 ){ paths.1 = path }
    return 
  }
  find_paths ( node.left, path + '/' + node.key )
  find_paths ( node.right, path + '/' + node.key )
}
// find paths 
find_paths( key1, key2, root, '' )
// split and now match 
paths.0 = paths.0.split('/')
paths.1 = paths.1.split('/')
#(s,l) = minmax ( paths ) :: { #|$.left| < #|$.right| }
inx = index ( [ #|s|-1:-1 ] ) :: {  
  paths[0][$.item] != paths[1][$.item]  
}
println( s[0][inx] )

Supposing the two integer values are not repeated:

private int num1, num2;
private Integer ancestor;




public int leastCommonAncestor(Node root, int num1, int num2){
	this.num1 = num1;
	this.num2 = num2;
	
	leastCommonAncestor(root);


	return ancestor;


}


private Integer leastCommonAncestor(Node node){
	if(node == null)
		return null;


	//Check if the ancestor is behind this node
	Integer left = leastCommonAncestor(node.left);
if(ancestor != null)
		return null;
	Integer right = leastCommonAncestor(node.left);
if(ancestor != null)
		return null;


	//Chech if the ancestor is this node
	if(left != null && right != null){
		ancestor = node.val;
		return  null;
	}


	//Check if the ancestor is this node, being also one of the numbers
	boolean isNum = (node.val == num1) || (node.val == num2);


	if((left != null || right != null) && isNum))
		ancestor = node.val;
		return null;
	}


//Return the num
if(left != null)
return left;
if(right != null)
return right;	
	
	if(isNum)
return node.val;


return null;	
	


}

import java.util.LinkedList;
public class LCA{
    
    public class Node {
        int info;
        Node left;
        Node right;
        
        public Node(int info) {
            this.info = info;
        }
    }
    
    Node lca;
    Node root;
    
    public void build() {
        root = new Node(1);
        Node two = new Node(2);
        Node three = new Node(3);
        root.left = two;
        root.right = three;
        
        Node four = new Node(4);
        Node five = new Node(5);
        Node six = new Node(6);
        Node seven = new Node(7);
    
        two.left = four;
        two.right = five;
        three.left = six;
        three.right = seven;
        
        four.left = new Node(9);
        five.right = new Node(10);
        
        seven.right = new Node(11);
    }
    
    public int lca(Node root, int n1, int n2) {
        if(root == null) {
            return 0;
        }
        
        if(root.info == n1 || root.info == n2) {
            return 1;
        }
        
        int l = lca(root.left, n1, n2);
        int r = lca(root.right, n1, n2);
        
        if(l == 1 && r == 1) {
            this.lca = root;
            return 2;
        }
        
        return l+r;
    }
    
    public void bfs() {
        LinkedList<Node> q = new LinkedList<>();
        q.add(root);
        doBfs(q);
    }
    
    public void doBfs(LinkedList<Node> q) {
        int len = q.size();
        
        if(len == 0) {
            return;
        }
        
        for(int i=0;i<len;i++) {
            Node t = q.removeFirst();
            System.out.println(t.info + " ");
            if(t.left != null) {
                q.addLast(t.left);
            }
            
            if(t.right != null) {
                q.addLast(t.right);
            }
        }
        
        System.out.println();
        doBfs(q);
    }

     public static void main(String []args){
        LCA test = new LCA();
        test.build();
        test.bfs();
        test.lca(test.root, 5,4);
        System.out.println(test.lca.info);
     }

}

This is an Objective-C solution using recursion

-(TreeNode *)getLowestCommonAncestor:(TreeNode *)root andNode1:(TreeNode *)n1 andNode2:(TreeNode *)n2{
    
    if(root == nil){
        return nil;
    }
    
    if(root == n1 || root == n2){
        return root;
    }
    
    TreeNode *leftNode = [self getLowestCommonAncestor:root.left andNode1:n1 andNode2:n2];
    
    TreeNode *rigthNode = [self getLowestCommonAncestor:root.rigth andNode1:n1 andNode2:n2];
    
    if(leftNode != nil && rigthNode != nil){
        
        return root;
    }
    else if(leftNode == nil && rigthNode == nil){
        
        return nil;
    }
    
    return leftNode != nil ? leftNode : rigthNode;
    
}

public void leastCommonPa(Node root, int n1, int n2){
HashMap<Integer, Integer> pa = new HashMap<>();
ArrayList<Node> queue = new ArrayList<>();
queue.add(root);
while(!queue.isEmpty()){
Node temp = queue.remove(0);
if(temp.left != null){
queue.add(temp.left);
pa.put(temp.left.value, temp.value);
}
if(temp.right != null){
queue.add(temp.right);
pa.put(temp.right.value, temp.value);
}
}
while(pa.get(n1) != pa.get(n2)){
System.out.println(pa.get(n1)+" "+pa.get(n2));
if(n1 == root.value || n2 == root.value)
break;
n1 = pa.get(n1);
n2 = pa.get(n2);
}
if(n1 == root.value || n2 == root.value)
System.out.println(root.value);
else
System.out.println(pa.get(n1));
}

using System.Collections.Generic;

public class Test
{
	static int lca = Int32.MinValue;
	class Node
	{
		public Node(int value, Node left, Node right)
		{
			Left = left;
			Right = right;
			Value = value;
		}
		
		public readonly Node Left;
		public readonly Node Right;
		public readonly int Value;
	}
	public static void Main()
	{
		// your code goes here
		var root = new Node(1, new Node(2, new Node(4, null, null), new Node(5, null, null)), 
							   new Node(3, new Node(6, null, null), new Node(7, null, null)));
		var itemsFound = Find (root , 6, 7);
		if(itemsFound == 2)
		{
			Console.Write(string.Format("LCA : {0}", lca));
		}
		else
		{
			Console.Write("NO LCA");
		}
		
		
	}
	
	private static int Find(Node root, int val1, int val2)
	{
		if(root == null) return 0;
		if(root.Value == val1 || root.Value == val2)
		{
			return 1;
		}
		
		int result  = Find(root.Left, val1, val2) + Find(root.Right, val1, val2);
		if(result == 2 && lca == Int32.MinValue)
		{
			lca = root.Value;
		}
		return result;
	}
}

public TreeNode getCommonAnchedtor(TreeNode n1, TreeNode n2){
        if (n1 == null || n2 == null || n1.parent == null || n2.parent == null) return null;
        boolean leftNode = true;
        if (n1.parent.right == n1) leftNode = false;
        
        TreeNode p = n1.parent;
        while (p.parent != null){
            if (leftNode) if (includedIn(p.parent.right,n2)) return p.parent;
            else if (includedIn(p.parent.left,n2)) return p.parent;
            p = p.parent;
        }
        
        return null;
    }
    
    public boolean includedIn(TreeNode n, TreeNode nSearch){
        if (n.left != null && includedIn(n.left,nSearch)) return true;
        if (n.right != null && includedIn(n.right,nSearch)) return true;
        if (n == nSearch) return true;
        return false;
    }

Least common ancestor node will have the value within <a, b> range.
If its value is below this range, the common ancestor is in the right
sub-tree. If it is above the range - look in the left sub-tree.

Node* FindCommonAncestor(Node* n, int a, int b)
{
    if (a > b)
	{
	    int tmp = a;
	    a = b;
	    b = a;
	}
	while (n != 0)
    {
	    if (n->val < a)
	        n = n->right;
	    else if (n->val > b)
	        n = n->left;
	    else
		    break;
    }
	return n;
}

This can be achieved in a single pass, without actually searching for the element.
We will use a simple property of a binary tree. At a particular node all elements at left will be smaller than the node and all elements at right will be bigger than the node. So this node will be LCA fo all combination of any node from left subtree and right subtree.
if both the values are less then traverse left if both values are greater then traverse right.
The solution proposed above is good but misses the case whe one of the two nodes is the LCA , so fixing the code

Node* FindCommonAncestor(Node* n, int a, int b)
{
    if (a > b)
	{
	    int tmp = a;
	    a = b;
	    b = a;
	}
	while (n != 0)
    {
	    if (n->val == a)
		break;
	    if (n->val < a)
	        n = n->right;
	    else if (n->val > b)
	        n = n->left;
	    else
		    break;
    }
	return n;
}

public BinaryTree F(BinaryTree root, int v1, int v2) {
            if (root == null)
                return null;
            if (root.data == v1 || root.data == v2)
                return root;

            var lr = F(root.left, v1, v2);
            var rr = F(root.right, v1, v2);

            if (lr != null && rr != null &&
                (lr.data == v1 || lr.data == v2) &&
                (rr.data == v1 || rr.data == v2) &&
                lr.data != rr.data)
                return root;
            if (lr != null)
                return lr;
            else
                return rr;

}

public static BinaryTree F(BinaryTree root, int v1, int v2) {
            if (root == null)
                return null;
            if (root.data == v1 || root.data == v2)
                return root;

            var lr = F(root.left, v1, v2);
            var rr = F(root.right, v1, v2);

            if (lr != null && rr != null &&
                (lr.data == v1 || lr.data == v2) &&
                (rr.data == v1 || rr.data == v2) &&
                lr.data != rr.data)
                return root;
            if (lr != null)
                return lr;
            else
                return rr;
        }