# Lowest common ancestor in a binary tree

Given a binary tree and find out the lowest common ancestor node using of two exist binary tree node. That is very interesting problem because trace Lowest common ancestor you need to write good logic. First let's see few test cases to find lowest ancestor in BST.

There are other case also possible when both node are not exist in binary tree or given both nodes are same.

Here given code implementation process.

``````/*
C Program
+ Lowest common ancestor in a binary tree
*/
#include<stdio.h>

#include<stdlib.h>
//structure of Binary Tree node
struct Node {
int data;
struct Node *left, *right;
};
//Create a binary tree nodes and node fields (data,pointer)
//And returning the reference of newly nodes

struct Node *insert(int data) {
//create dynamic memory to new binary tree node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL) {
//set data and pointer values
new_node->data = data;
new_node->left = NULL; //Initially node left-pointer is NULL
new_node->right = NULL; //Initially node right-pointer is NULL
} else {
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
//return reference
return new_node;

}
//find given node value exist or not
int findNode(struct Node *node, int data) {
if (node != NULL) {
if (node->data == data) {
return 1;
} else {
return (findNode(node->left, data) || findNode(node->right, data));
}
} else {
return 0;
}
}
//Check LCA of two binary tree nodes
void LCA(struct Node *node, int start, int end) {

if (node != NULL) {

if (node->data == start) {
if (findNode(node, end)) {
printf("Node [%d , %d]  LCA : %d\n", start, end, node->data);
} else {
printf("Node [%d , %d] : Opps node data %d are not exist \n", start, end, end);
}

} else if (node->data == end) {
if (findNode(node, start)) {
printf("Node [%d , %d]  LCA : %d\n", start, end, node->data);
} else {
printf("Node [%d , %d] : Opps node data %d are not exist \n", start, end, start);
}
} else {
int left = findNode(node->left, start);
int right = findNode(node->right, end);

if (left == 0 && right == 0) {
//again trace with value change
left = findNode(node->left, end);
right = findNode(node->right, start);

}
if (left == 1 && right == 1) {
printf("Node [%d , %d]  LCA : %d\n", start, end, node->data);
} else if (left == 0 && right == 0) {
//That means given node values are not existing in this binary tree
printf("Node [%d , %d] : Both node values are not exist\n", start, end);
return;
} else if (left != 0) {
LCA(node->left, start, end);
} else {
LCA(node->right, start, end);
}
}
}
}

int main() {

struct Node *root = NULL;
int position = 4;
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
*/
//Insertion of binary tree nodes
root = insert(1);
root->left = insert(2);
root->right = insert(3);
root->right->right = insert(6);
root->right->left = insert(5);
root->left->left = insert(4);
root->left->left->right = insert(7);
root->right->right->left = insert(8);
//test case
LCA(root, 8, 5);
LCA(root, 7, 2);
LCA(root, 7, 8);
LCA(root, 3, 7);
LCA(root, 15, 4);
LCA(root, 7, 9);
LCA(root, 11, 9);
LCA(root, 5, 5);
return 0;
}```
```

#### Output

``````Node [8 , 5]  LCA : 3
Node [7 , 2]  LCA : 2
Node [7 , 8]  LCA : 1
Node [3 , 7]  LCA : 1
Node [15 , 4] : Opps node data 15 are not exist
Node [7 , 9] : Opps node data 9 are not exist
Node [11 , 9] : Both node values are not exist
Node [5 , 5]  LCA : 5
``````
``````/*
C++ Program
Lowest common ancestor in a binary tree
*/

#include<iostream>

using namespace std;
class Node {
public:
int data;
Node *left, *right;
Node(int value) {
data = value;
left = right = NULL;
}
};
class BinaryTree {
public:
Node *root;
BinaryTree() {
this->root = NULL;
}
bool findNode(Node *node, int value) {
if (node != NULL) {
if (node->data == value) {
return true;
} else {
return (this->findNode(node->left, value) || this->findNode(node->right, value));
}
}
return false;
}
void lca(Node *node, int start, int end) {
if (node != NULL) {
if (node->data == start) {
if (this->findNode(node, end)) {
cout << "Node [" << start << " , " << end << "]  LCA : " << node->data << "\n";
} else {
cout << "Node [" << start << " , " << end << "]  : Opps node data " << end << " are not exist \n";
}
} else
if (node->data == end) {
if (this->findNode(node, start)) {
cout << "Node [" << start << " , " << end << "]  LCA : " << node->data << "\n";
} else {
cout << "Node [" << start << " , " << end << "]  : Opps node data " << start << " are not exist \n";
}
} else {
bool left_child = this->findNode(node->left, start);
bool right_child = this->findNode(node->right, end);
if (left_child == false && right_child == false) {
left_child = this->findNode(node->left, end);
right_child = this->findNode(node->right, start);
}
if (left_child == true && right_child == true) {
cout << "Node [" << start << " , " << end << "]  LCA : " << node->data << "\n";
} else
if (left_child == false && right_child == false) {
cout << "Node [" << start << " , " << end << "]  : Both node values are not exist \n";
return;
} else
if (left_child != false) {
this->lca(node->left, start, end);
} else {
this->lca(node->right, start, end);
}
}
}
}
};
int main() {
BinaryTree obj ;
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
*/
obj.root = new Node(1);
obj.root->left = new Node(2);
obj.root->right = new Node(3);
obj.root->right->right = new Node(6);
obj.root->right->left = new Node(5);
obj.root->left->left = new Node(4);
obj.root->left->left->right = new Node(7);
obj.root->right->right->left = new Node(8);
obj.lca(obj.root, 8, 5);
obj.lca(obj.root, 7, 2);
obj.lca(obj.root, 7, 8);
obj.lca(obj.root, 3, 7);
obj.lca(obj.root, 15, 4);
obj.lca(obj.root, 7, 9);
obj.lca(obj.root, 11, 9);
obj.lca(obj.root, 5, 5);

return 0;
}```
```

#### Output

``````Node [8 , 5]  LCA : 3
Node [7 , 2]  LCA : 2
Node [7 , 8]  LCA : 1
Node [3 , 7]  LCA : 1
Node [15 , 4] : Opps node data 15 are not exist
Node [7 , 9] : Opps node data 9 are not exist
Node [11 , 9] : Both node values are not exist
Node [5 , 5]  LCA : 5
``````
``````/*
Java Program
Lowest common ancestor in a binary tree
*/

//Class of Binary Tree Node
class Node {

public int data;

public Node left, right;
//Make a tree TreeNode
public Node(int value) {
//Assign field values
data = value;
left = right = null;
}
}

public class BinaryTree {

public Node root;

public BinaryTree() {
//Set initial values
root = null;

}
//Find given node value exist or not
public boolean findNode(Node node, int value) {
if (node != null) {
if (node.data == value) {
return true;
} else {
return (findNode(node.left, value) || findNode(node.right, value));
}
}

return false;

}
//Check LCA of two binary tree nodes
public void lca(Node node, int start, int last) {

if (node != null) {

if (node.data == start) {
if (findNode(node, last)) {
System.out.print("Node [" + start + " , " + last + "]  LCA : " + node.data + "\n");
} else {

System.out.print("Node [" + start + " , " + last + "]  : Opps node data " + last + " are not exist \n");
}
} else if (node.data == last) {
if (findNode(node, start)) {
System.out.print("Node [" + start + " , " + last + "]  LCA : " + node.data + "\n");
} else {
System.out.print("Node [" + start + " , " + last + "]  : Opps node data " + start + " are not exist \n");
}
} else {
boolean left_child = findNode(node.left, start);
boolean right_child = findNode(node.right, last);

if (left_child == false && right_child == false) {
//again trace with value change
left_child = findNode(node.left, last);
right_child = findNode(node.right, start);

}
if (left_child == true && right_child == true) {
System.out.print("Node [" + start + " , " + last + "]  LCA : " + node.data + "\n");
} else if (left_child == false && right_child == false) {
//That means given node values are not existing in this binary tree

System.out.print("Node [" + start + " , " + last + "]  : Both node values are not exist \n");

return;
} else if (left_child != false) {
lca(node.left, start, last);
} else {
lca(node.right, start, last);
}
}
}
}

public static void main(String[] args) {
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
*/
//Binary tree nodes
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.left.left = new Node(4);
obj.root.left.left.right = new Node(7);
obj.root.right.right.left = new Node(8);
//test case
obj.lca(obj.root, 8, 5);
obj.lca(obj.root, 7, 2);
obj.lca(obj.root, 7, 8);
obj.lca(obj.root, 3, 7);
obj.lca(obj.root, 15, 4);
obj.lca(obj.root, 7, 9);
obj.lca(obj.root, 11, 9);
obj.lca(obj.root, 5, 5);

}
}```
```

#### Output

``````Node [8 , 5]  LCA : 3
Node [7 , 2]  LCA : 2
Node [7 , 8]  LCA : 1
Node [3 , 7]  LCA : 1
Node [15 , 4] : Opps node data 15 are not exist
Node [7 , 9] : Opps node data 9 are not exist
Node [11 , 9] : Both node values are not exist
Node [5 , 5]  LCA : 5
``````
``````/*
C# Program
Lowest common ancestor in a binary tree
*/
using System;
//Class of Binary Tree Node
public class Node {

public int data;

public Node left, right;
//Make a tree TreeNode
public Node(int value) {
//Assign field values
data = value;
left = right = null;
}
}

public class BinaryTree {

public Node root;

public BinaryTree() {
//Set initial values
root = null;

}
//Find given node value exist or not
public Boolean findNode(Node node, int value) {
if (node != null) {
if (node.data == value) {
return true;
} else {
return (findNode(node.left, value) || findNode(node.right, value));
}
}

return false;

}
//Check LCA of two binary tree nodes
public void lca(Node node, int start, int last) {

if (node != null) {

if (node.data == start) {
if (findNode(node, last)) {
Console.Write("Node [" + start + " , " + last + "]  LCA : " + node.data + "\n");
} else {

Console.Write("Node [" + start + " , " + last + "]  : Opps node data " + last + " are not exist \n");
}
} else if (node.data == last) {
if (findNode(node, start)) {
Console.Write("Node [" + start + " , " + last + "]  LCA : " + node.data + "\n");
} else {
Console.Write("Node [" + start + " , " + last + "]  : Opps node data " + start + " are not exist \n");
}
} else {
Boolean left_child = findNode(node.left, start);
Boolean right_child = findNode(node.right, last);

if (left_child == false && right_child == false) {
//again trace with value change
left_child = findNode(node.left, last);
right_child = findNode(node.right, start);

}
if (left_child == true && right_child == true) {
Console.Write("Node [" + start + " , " + last + "]  LCA : " + node.data + "\n");
} else if (left_child == false && right_child == false) {
//That means given node values are not existing in this binary tree

Console.Write("Node [" + start + " , " + last + "]  : Both node values are not exist \n");

return;
} else if (left_child != false) {
lca(node.left, start, last);
} else {
lca(node.right, start, last);
}
}
}
}

public static void Main(String[] args) {
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
*/
//Binary tree nodes
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.left.left = new Node(4);
obj.root.left.left.right = new Node(7);
obj.root.right.right.left = new Node(8);
//test case
obj.lca(obj.root, 8, 5);
obj.lca(obj.root, 7, 2);
obj.lca(obj.root, 7, 8);
obj.lca(obj.root, 3, 7);
obj.lca(obj.root, 15, 4);
obj.lca(obj.root, 7, 9);
obj.lca(obj.root, 11, 9);
obj.lca(obj.root, 5, 5);

}
}```
```

#### Output

``````Node [8 , 5]  LCA : 3
Node [7 , 2]  LCA : 2
Node [7 , 8]  LCA : 1
Node [3 , 7]  LCA : 1
Node [15 , 4] : Opps node data 15 are not exist
Node [7 , 9] : Opps node data 9 are not exist
Node [11 , 9] : Both node values are not exist
Node [5 , 5]  LCA : 5
``````
``````#Python Program
#Lowest common ancestor in a binary tree
class Node :

def __init__(self, value) :
self.data = value
self.left = self.right = None

class BinaryTree :

def __init__(self) :
self.root = None

def findNode(self, node, value) :
if (node != None) :
if (node.data == value) :
return True
else :
return (self.findNode(node.left, value) or self.findNode(node.right, value))

return False

def lca(self, node, start, last) :
if (node != None) :
if (node.data == start) :
if (self.findNode(node, last)) :
print("Node [", start ," , ", last ,"]  LCA : ", node.data )
else :
print("Node [", start ," , ", last ,"]  : Opps node data ", last ," are not exist ")

elif (node.data == last) :
if (self.findNode(node, start)) :
print("Node [", start ," , ", last ,"]  LCA : ", node.data )
else :
print("Node [", start ," , ", last ,"]  : Opps node data ", start ," are not exist ")

else :
left_child = self.findNode(node.left, start)
right_child = self.findNode(node.right, last)
if (left_child == False and right_child == False) :
left_child = self.findNode(node.left, last)
right_child = self.findNode(node.right, start)

if (left_child == True and right_child == True) :
print("Node [", start ," , ", last ,"]  LCA : ", node.data )
elif (left_child == False and right_child == False) :
print("Node [", start ," , ", last ,"]  : Both node values are not exist ")
return
elif (left_child != False) :
self.lca(node.left, start, last)
else :
self.lca(node.right, start, last)

def main() :
obj = BinaryTree()

# Make A Binary Tree
#
#          1
#         /  \
#        2    3
#       /    /  \
#      4    5    6
#       \       /
#        7     8
#
obj.root = Node(1)
obj.root.left = Node(2)
obj.root.right = Node(3)
obj.root.right.right = Node(6)
obj.root.right.left = Node(5)
obj.root.left.left = Node(4)
obj.root.left.left.right = Node(7)
obj.root.right.right.left = Node(8)
obj.lca(obj.root, 8, 5)
obj.lca(obj.root, 7, 2)
obj.lca(obj.root, 7, 8)
obj.lca(obj.root, 3, 7)
obj.lca(obj.root, 15, 4)
obj.lca(obj.root, 7, 9)
obj.lca(obj.root, 11, 9)
obj.lca(obj.root, 5, 5)

if __name__ == "__main__":
main()```
```

#### Output

``````Node [8 , 5]  LCA : 3
Node [7 , 2]  LCA : 2
Node [7 , 8]  LCA : 1
Node [3 , 7]  LCA : 1
Node [15 , 4] : Opps node data 15 are not exist
Node [7 , 9] : Opps node data 9 are not exist
Node [11 , 9] : Both node values are not exist
Node [5 , 5]  LCA : 5
``````
``````# Ruby Program
# Lowest common ancestor in a binary tree
class Node
attr_accessor :data, :left, :right
def initialize(value)
@data = value
@left = @right = nil
end
end

class BinaryTree
attr_accessor :root
def initialize()
@root = nil
end
def findNode(node, value)
if (node != nil)
if (node.data == value)
return true
else
return (self.findNode(node.left, value) or self.findNode(node.right, value))
end
end
return false
end
def lca(node, start, last)
if (node != nil)
if (node.data == start)
if (self.findNode(node, last))
print("Node [", start ," , ", last ,"]  LCA  :", node.data ,"\n")
else
print("Node [", start ," , ", last ,"]   :Opps node data ", last ," are not exist \n")
end
elsif (node.data == last)
if (self.findNode(node, start))
print("Node [", start ," , ", last ,"]  LCA  :", node.data ,"\n")
else
print("Node [", start ," , ", last ,"]   :Opps node data ", start ," are not exist \n")
end
else
left_child = self.findNode(node.left, start)
right_child = self.findNode(node.right, last)
if (left_child == false and right_child == false)
left_child = self.findNode(node.left, last)
right_child = self.findNode(node.right, start)
end
if (left_child == true and right_child == true)
print("Node [", start ," , ", last ,"]  LCA  :", node.data ,"\n")
elsif (left_child == false and right_child == false)
print("Node [", start ," , ", last ,"]   :Both node values are not exist \n")
return
elsif (left_child != false)
self.lca(node.left, start, last)
else
self.lca(node.right, start, last)
end
end
end
end

end
def main()
obj = BinaryTree.new()
# Make A Binary Tree
#
#          1
#         /  \
#        2    3
#       /    /  \
#      4    5    6
#       \       /
#        7     8
#
obj.root = Node.new(1)
obj.root.left = Node.new(2)
obj.root.right = Node.new(3)
obj.root.right.right = Node.new(6)
obj.root.right.left = Node.new(5)
obj.root.left.left = Node.new(4)
obj.root.left.left.right = Node.new(7)
obj.root.right.right.left = Node.new(8)
obj.lca(obj.root, 8, 5)
obj.lca(obj.root, 7, 2)
obj.lca(obj.root, 7, 8)
obj.lca(obj.root, 3, 7)
obj.lca(obj.root, 15, 4)
obj.lca(obj.root, 7, 9)
obj.lca(obj.root, 11, 9)
obj.lca(obj.root, 5, 5)
end
main()```
```

#### Output

``````Node [8 , 5]  LCA : 3
Node [7 , 2]  LCA : 2
Node [7 , 8]  LCA : 1
Node [3 , 7]  LCA : 1
Node [15 , 4] : Opps node data 15 are not exist
Node [7 , 9] : Opps node data 9 are not exist
Node [11 , 9] : Both node values are not exist
Node [5 , 5]  LCA : 5
``````
``````<?php
/*
Php Program
Lowest common ancestor in a binary tree
*/
class Node {
public \$data;
public \$left;
public \$right;

function __construct(\$value) {
\$this->data = \$value;
\$this->left = \$this->right = null;
}
}
class BinaryTree {
public \$root;

function __construct() {
\$this->root = null;
}
public  function findNode(\$node, \$value) {
if (\$node != null) {
if (\$node->data == \$value) {
return true;
} else {
return (\$this->findNode(\$node->left, \$value) || \$this->findNode(\$node->right, \$value));
}
}
return false;
}
public  function lca(\$node, \$start, \$last) {
if (\$node != null) {
if (\$node->data == \$start) {
if (\$this->findNode(\$node, \$last)) {
echo("Node [". \$start ." , ". \$last ."]  LCA : ". \$node->data ."\n");
} else {
echo("Node [". \$start ." , ". \$last ."]  : Opps node data ". \$last ." are not exist \n");
}
} else
if (\$node->data == \$last) {
if (\$this->findNode(\$node, \$start)) {
echo("Node [". \$start ." , ". \$last ."]  LCA : ". \$node->data ."\n");
} else {
echo("Node [". \$start ." , ". \$last ."]  : Opps node data ". \$start ." are not exist \n");
}
} else {
\$left_child = \$this->findNode(\$node->left, \$start);
\$right_child = \$this->findNode(\$node->right, \$last);
if (\$left_child == false && \$right_child == false) {
\$left_child = \$this->findNode(\$node->left, \$last);
\$right_child = \$this->findNode(\$node->right, \$start);
}
if (\$left_child == true && \$right_child == true) {
echo("Node [". \$start ." , ". \$last ."]  LCA : ". \$node->data ."\n");
} else
if (\$left_child == false && \$right_child == false) {
echo("Node [". \$start ." , ". \$last ."]  : Both node values are not exist \n");
return;
} else
if (\$left_child != false) {
\$this->lca(\$node->left, \$start, \$last);
} else {
\$this->lca(\$node->right, \$start, \$last);
}
}
}
}
}
function main() {
\$obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
*/
\$obj->root = new Node(1);
\$obj->root->left = new Node(2);
\$obj->root->right = new Node(3);
\$obj->root->right->right = new Node(6);
\$obj->root->right->left = new Node(5);
\$obj->root->left->left = new Node(4);
\$obj->root->left->left->right = new Node(7);
\$obj->root->right->right->left = new Node(8);
\$obj->lca(\$obj->root, 8, 5);
\$obj->lca(\$obj->root, 7, 2);
\$obj->lca(\$obj->root, 7, 8);
\$obj->lca(\$obj->root, 3, 7);
\$obj->lca(\$obj->root, 15, 4);
\$obj->lca(\$obj->root, 7, 9);
\$obj->lca(\$obj->root, 11, 9);
\$obj->lca(\$obj->root, 5, 5);
}
main();```
```

#### Output

``````Node [8 , 5]  LCA : 3
Node [7 , 2]  LCA : 2
Node [7 , 8]  LCA : 1
Node [3 , 7]  LCA : 1
Node [15 , 4] : Opps node data 15 are not exist
Node [7 , 9] : Opps node data 9 are not exist
Node [11 , 9] : Both node values are not exist
Node [5 , 5]  LCA : 5
``````
``````/*
Node JS Program
Lowest common ancestor in a binary tree
*/
class Node {

constructor(value) {
this.data = value;
this.left = this.right = null;
}
}
class BinaryTree {

constructor() {
this.root = null;
}
findNode(node, value) {
if (node != null) {
if (node.data == value) {
return true;
} else {
return (this.findNode(node.left, value) || this.findNode(node.right, value));
}
}
return false;
}
lca(node, start, last) {
if (node != null) {
if (node.data == start) {
if (this.findNode(node, last)) {
process.stdout.write("Node [" + start + " , " + last + "]  LCA : " + node.data + "\n");
} else {
process.stdout.write("Node [" + start + " , " + last + "]  : Opps node data " + last + " are not exist \n");
}
} else
if (node.data == last) {
if (this.findNode(node, start)) {
process.stdout.write("Node [" + start + " , " + last + "]  LCA : " + node.data + "\n");
} else {
process.stdout.write("Node [" + start + " , " + last + "]  : Opps node data " + start + " are not exist \n");
}
} else {
var left_child = this.findNode(node.left, start);
var right_child = this.findNode(node.right, last);
if (left_child == false && right_child == false) {
left_child = this.findNode(node.left, last);
right_child = this.findNode(node.right, start);
}
if (left_child == true && right_child == true) {
process.stdout.write("Node [" + start + " , " + last + "]  LCA : " + node.data + "\n");
} else
if (left_child == false && right_child == false) {
process.stdout.write("Node [" + start + " , " + last + "]  : Both node values are not exist \n");
return;
} else
if (left_child != false) {
this.lca(node.left, start, last);
} else {
this.lca(node.right, start, last);
}
}
}
}
}

function main() {
var obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
*/
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.left.left = new Node(4);
obj.root.left.left.right = new Node(7);
obj.root.right.right.left = new Node(8);
obj.lca(obj.root, 8, 5);
obj.lca(obj.root, 7, 2);
obj.lca(obj.root, 7, 8);
obj.lca(obj.root, 3, 7);
obj.lca(obj.root, 15, 4);
obj.lca(obj.root, 7, 9);
obj.lca(obj.root, 11, 9);
obj.lca(obj.root, 5, 5);
}
main();```
```

#### Output

``````Node [8 , 5]  LCA : 3
Node [7 , 2]  LCA : 2
Node [7 , 8]  LCA : 1
Node [3 , 7]  LCA : 1
Node [15 , 4] : Opps node data 15 are not exist
Node [7 , 9] : Opps node data 9 are not exist
Node [11 , 9] : Both node values are not exist
Node [5 , 5]  LCA : 5
``````
``````/*
Swift 4 Program
Lowest common ancestor in a binary tree
*/
class Node {
var data: Int;
var left: Node? ;
var right: Node? ;

init(_ value: Int) {
self.data = value;
self.left = nil;
self.right = nil;
}
}
class BinaryTree {
var root: Node? ;
init() {
self.root = nil;
}
func findNode(_ node: Node? , _ value : Int) -> Bool {
if (node != nil) {
if (node!.data == value) {
return true;
} else {
return (self.findNode(node!.left, value) || self.findNode(node!.right, value));
}
}
return false;
}
func lca(_ node: Node? , _ start : Int, _ last: Int) {
if (node != nil) {
if (node!.data == start) {
if (self.findNode(node, last)) {
print("Node [", start ," , ", last ,"]  LCA : ", node!.data ,"\n");
} else {
print("Node [", start ," , ", last ,"]  : Opps node data ", last ," are not exist \n");
}
} else
if (node!.data == last) {
if (self.findNode(node, start)) {
print("Node [", start ," , ", last ,"]  LCA : ", node!.data ,"\n");
} else {
print("Node [", start ," , ", last ,"]  : Opps node data ", start ," are not exist \n");
}
} else {
var left_child: Bool = self.findNode(node!.left, start);
var right_child: Bool = self.findNode(node!.right, last);
if (left_child == false && right_child == false) {
left_child = self.findNode(node!.left, last);
right_child = self.findNode(node!.right, start);
}
if (left_child == true && right_child == true) {
print("Node [", start ," , ", last ,"]  LCA : ", node!.data ,"\n");
} else
if (left_child == false && right_child == false) {
print("Node [", start ," , ", last ,"]  : Both node values are not exist \n");
return;
} else
if (left_child != false) {
self.lca(node!.left, start, last);
} else {
self.lca(node!.right, start, last);
}
}
}
}
}
func main() {
let obj: BinaryTree = BinaryTree();
obj.root = Node(1);
obj.root!.left = Node(2);
obj.root!.right = Node(3);
obj.root!.right!.right = Node(6);
obj.root!.right!.left = Node(5);
obj.root!.left!.left = Node(4);
obj.root!.left!.left!.right = Node(7);
obj.root!.right!.right!.left = Node(8);
obj.lca(obj.root, 8, 5);
obj.lca(obj.root, 7, 2);
obj.lca(obj.root, 7, 8);
obj.lca(obj.root, 3, 7);
obj.lca(obj.root, 15, 4);
obj.lca(obj.root, 7, 9);
obj.lca(obj.root, 11, 9);
obj.lca(obj.root, 5, 5);
}
main();```
```

#### Output

``````Node [8 , 5]  LCA : 3
Node [7 , 2]  LCA : 2
Node [7 , 8]  LCA : 1
Node [3 , 7]  LCA : 1
Node [15 , 4] : Opps node data 15 are not exist
Node [7 , 9] : Opps node data 9 are not exist
Node [11 , 9] : Both node values are not exist
Node [5 , 5]  LCA : 5
``````

We can optimize above solution in this way.

``````/*
C Program
Lowest common ancestor in a binary tree set B
When Assume that given node is exist in tree
*/
#include <stdio.h>

#include <stdlib.h>
//structure of Binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};
//Create a binary tree nodes and node fields (data,pointer)
//And returning the reference of newly nodes
struct Node *insert(int data)
{
//create dynamic memory to new binary tree node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//set data and pointer values
new_node->data = data;
new_node->left = NULL; //Initially node left-pointer is NULL
new_node->right = NULL; //Initially node right-pointer is NULL
}
else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
//return reference
return new_node;
}
//This function are finding the LCA of given two  node
struct Node *lca(struct Node *root, int node1, int node2)
{
if (root != NULL)
{
if (root->data == node1 || root->data == node2)
{
//When tree node data is equal to node1 or value node2
return root;
}
//here first and second variable are contain the information of
//left and right subtree when it is contain the given value
struct Node *first = lca(root->left, node1, node2);
struct Node *second = lca(root->right, node1, node2);
if (first != NULL && second != NULL)
{
//When first and second subtree contains node values
//This condition is based on post order traversal so current node is resultant of LCA initial
return root;
}
if (first != NULL)
{
//When first subtree contains result
return first;
}
// return the result of second subtree
return second;
}
else
{
//When tree node are empty [null]
return NULL;
}
}
//This function are handle the request of find LCA of two tree nodes
void find_lca(struct Node *root, int node1, int node2)
{
//Display node value
printf("\nNodes [%d, %d] ", node1, node2);
struct Node *status = lca(root, node1, node2);
if (status != NULL)
{
printf(" LCA : %d\n", status->data);
}
else
{
printf("Pair are missing \n");
}
}
int main()
{
struct Node *root = NULL;
/*Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
*/
//Insertion of binary tree nodes
root = insert(1);
root->left = insert(2);
root->right = insert(3);
root->right->right = insert(6);
root->right->left = insert(5);
root->left->left = insert(4);
root->left->left->right = insert(7);
root->right->right->left = insert(8);
//test case
find_lca(root, 8, 5);
find_lca(root, 7, 2);
find_lca(root, 7, 8);
find_lca(root, 3, 7);
find_lca(root, 5, 5);
find_lca(root, 4, 5);
return 0;
}``````

#### Output

``````Nodes [8, 5]  LCA : 3

Nodes [7, 2]  LCA : 2

Nodes [7, 8]  LCA : 1

Nodes [3, 7]  LCA : 1

Nodes [5, 5]  LCA : 5

Nodes [4, 5]  LCA : 1``````
``````/*
Java Program
Lowest common ancestor in a binary tree
*/
//Class of Binary Tree Node
class Node
{
public int data;
public Node left, right;
//Make a tree TreeNode
public Node(int value)
{
//Assign field values
data = value;
left = null;
right = null;
}
}
class BinaryTree
{
public Node root;
public BinaryTree()
{
//Set initial values
root = null;
}
//This function are finding the LCA of given two  node
public Node lca(Node root, int node1, int node2)
{
if (root != null)
{
if (root.data == node1 || root.data == node2)
{
//When tree node data is equal to node1 or value node2
return root;
}
//here first and second variable are contain the information of
//left and right subtree when it is contain the given value
Node first = lca(root.left, node1, node2);
Node second = lca(root.right, node1, node2);
if (first != null && second != null)
{
//When first and second subtree contains node values
//This condition is based on post order traversal so current node is resultant of LCA initial
return root;
}
if (first != null)
{
//When first subtree contains result
return first;
}
// return the result of second subtree
return second;
}
else
{
//When tree node are empty [null]
return null;
}
}
//This function are handle the request of find LCA of two tree nodes
public void find_lca(int node1, int node2)
{
//Display node value
System.out.print("\nNodes [" + node1 + ", " + node2 + "] ");
Node result = lca(root, node1, node2);
if (result != null)
{
System.out.print(" LCA : " + result.data + "\n");
}
else
{
System.out.print("Pair are missing \n");
}
}
public static void main(String[] args)
{
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
*/
//Binary tree nodes
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.left.left = new Node(4);
obj.root.left.left.right = new Node(7);
obj.root.right.right.left = new Node(8);
//test case
obj.find_lca(8, 5);
obj.find_lca(7, 2);
obj.find_lca(7, 8);
obj.find_lca(3, 7);
obj.find_lca(5, 5);
obj.find_lca(4, 5);
}
}``````

#### Output

``````Nodes [8, 5]  LCA : 3

Nodes [7, 2]  LCA : 2

Nodes [7, 8]  LCA : 1

Nodes [3, 7]  LCA : 1

Nodes [5, 5]  LCA : 5

Nodes [4, 5]  LCA : 1``````
``````/*
C++ Program
Lowest common ancestor in a binary tree
*/
//Class of Binary Tree Node
#include<iostream>

using namespace std;
class Node
{
public: int data;
Node *left, *right;
//Make a tree TreeNode
Node(int value)
{
//Assign field values
this->data = value;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public: Node *root;
BinaryTree()
{
//Set initial values
this->root = NULL;
}
//This function are finding the LCA of given two  node
Node* lca(Node *root, int node1, int node2)
{
if (root != NULL)
{
if (root->data == node1 || root->data == node2)
{
//When tree node data is equal to node1 or value node2
return root;
}
//here first and second variable are contain the information of
//left and right subtree when it is contain the given value
Node *first = lca(root->left, node1, node2);
Node *second = lca(root->right, node1, node2);
if (first != NULL && second != NULL)
{
//When first and second subtree contains node values
//This condition is based on post order traversal so current node is resultant of LCA initial
return root;
}
if (first != NULL)
{
//When first subtree contains result
return first;
}
// return the result of second subtree
return second;
}
else
{
//When tree node are empty [null]
return NULL;
}
}
//This function are handle the request of find LCA of two tree nodes
void find_lca(int node1, int node2)
{
cout << "\nNodes [" << node1 << ", " << node2 << "] ";
Node *result = lca(this->root, node1, node2);
if (result != NULL)
{
cout << " LCA : " << result->data << "\n";
}
else
{
cout << "Pair are missing \n";
}
}
};
int main()
{
//Make object of Binary Tree
BinaryTree obj;
/*Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
*/
//Binary tree nodes
obj.root = new Node(1);
obj.root->left = new Node(2);
obj.root->right = new Node(3);
obj.root->right->right = new Node(6);
obj.root->right->left = new Node(5);
obj.root->left->left = new Node(4);
obj.root->left->left->right = new Node(7);
obj.root->right->right->left = new Node(8);
//test case
obj.find_lca(8, 5);
obj.find_lca(7, 2);
obj.find_lca(7, 8);
obj.find_lca(3, 7);
obj.find_lca(5, 5);
obj.find_lca(4, 5);
return 0;
}``````

#### Output

``````Nodes [8, 5]  LCA : 3

Nodes [7, 2]  LCA : 2

Nodes [7, 8]  LCA : 1

Nodes [3, 7]  LCA : 1

Nodes [5, 5]  LCA : 5

Nodes [4, 5]  LCA : 1``````
``````/*
C# Program
Lowest common ancestor in a binary tree
*/
//Class of Binary Tree Node
using System;
class Node
{
public int data;
public Node left, right;
//Make a tree TreeNode
public Node(int value)
{
//Assign field values
data = value;
left = null;
right = null;
}
}
class BinaryTree
{
public Node root;
public BinaryTree()
{
//Set initial values
root = null;
}
//This function are finding the LCA of given two  node
public Node lca(Node root, int node1, int node2)
{
if (root != null)
{
if (root.data == node1 || root.data == node2)
{
return root;
}
//here first and second variable are contain the information of
//left and right subtree when it is contain the given value
Node first = lca(root.left, node1, node2);
Node second = lca(root.right, node1, node2);
if (first != null && second != null)
{
return root;
}
if (first != null)
{
return first;
}
return second;
}
else
{
return null;
}
}
//This function are handle the request of find LCA of two tree nodes
public void find_lca(int node1, int node2)
{
Console.Write("\nNodes [" + node1 + ", " + node2 + "] ");
Node result = lca(root, node1, node2);
if (result != null)
{
Console.Write(" LCA : " + result.data + "\n");
}
else
{
Console.Write("Pair are missing \n");
}
}
public static void Main(String[] args)
{
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
*/
//Binary tree nodes
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.left.left = new Node(4);
obj.root.left.left.right = new Node(7);
obj.root.right.right.left = new Node(8);
//test case
obj.find_lca(8, 5);
obj.find_lca(7, 2);
obj.find_lca(7, 8);
obj.find_lca(3, 7);
obj.find_lca(5, 5);
obj.find_lca(4, 5);
}
}``````

#### Output

``````Nodes [8, 5]  LCA : 3

Nodes [7, 2]  LCA : 2

Nodes [7, 8]  LCA : 1

Nodes [3, 7]  LCA : 1

Nodes [5, 5]  LCA : 5

Nodes [4, 5]  LCA : 1``````
``````<?php
/*
Php Program
Lowest common ancestor in a binary tree
*/
//Class of Binary Tree Node
class Node
{
public \$data;
public \$left;
public \$right;
//Make a tree TreeNode
function __construct(\$value)
{
//Assign field values
\$this->data = \$value;
\$this->left = null;
\$this->right = null;
}
}
class BinaryTree
{
public \$root;

function __construct()
{
//Set initial values
\$this->root = null;
}
//This function are finding the LCA of given two  node
public  function lca(\$root, \$node1, \$node2)
{
if (\$root != null)
{
if (\$root->data == \$node1 || \$root->data == \$node2)
{

//When tree node data is equal to node1 or value node2
return \$root;
}
//here first and second variable are contain the information of
//left and right subtree when it is contain the given value
\$first = \$this->lca(\$root->left, \$node1, \$node2);
\$second = \$this->lca(\$root->right, \$node1, \$node2);
if (\$first != null && \$second != null)
{

//When first and second subtree contains node values
//This condition is based on post order traversal so current node is resultant of LCA initial
return \$root;
}
if (\$first != null)
{

//When first subtree contains result
return \$first;
}

// return the result of second subtree
return \$second;
}
else
{

//When tree node are empty [null]
return null;
}
}
//This function are handle the request of find LCA of two tree nodes
public  function find_lca(\$node1, \$node2)
{
echo "\nNodes [". \$node1 .", ". \$node2 ."] ";
\$result = \$this->lca(\$this->root, \$node1, \$node2);
if (\$result != null)
{
echo " LCA : ". \$result->data ."\n";
}
else
{
echo "Pair are missing \n";
}
}
}

function main()
{
//Make object of Binary Tree
\$obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
*/
//Binary tree nodes
\$obj->root = new Node(1);
\$obj->root->left = new Node(2);
\$obj->root->right = new Node(3);
\$obj->root->right->right = new Node(6);
\$obj->root->right->left = new Node(5);
\$obj->root->left->left = new Node(4);
\$obj->root->left->left->right = new Node(7);
\$obj->root->right->right->left = new Node(8);
//test case
\$obj->find_lca(8, 5);
\$obj->find_lca(7, 2);
\$obj->find_lca(7, 8);
\$obj->find_lca(3, 7);
\$obj->find_lca(5, 5);
\$obj->find_lca(4, 5);
}
main();``````

#### Output

``````Nodes [8, 5]  LCA : 3

Nodes [7, 2]  LCA : 2

Nodes [7, 8]  LCA : 1

Nodes [3, 7]  LCA : 1

Nodes [5, 5]  LCA : 5

Nodes [4, 5]  LCA : 1``````
``````/*
Node Js Program
Lowest common ancestor in a binary tree
*/
//Class of Binary Tree Node
class Node
{
//Make a tree TreeNode
constructor(value)
{
//Assign field values
this.data = value;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
//Set initial values
this.root = null;
}
//This function are finding the LCA of given two  node
lca(root, node1, node2)
{
if (root != null)
{
if (root.data == node1 || root.data == node2)
{

//When tree node data is equal to node1 or value node2
return root;
}
//here first and second variable are contain the information of
//left and right subtree when it is contain the given value
var first = this.lca(root.left, node1, node2);
var second = this.lca(root.right, node1, node2);
if (first != null && second != null)
{

//When first and second subtree contains node values
//This condition is based on post order traversal so current node is resultant of LCA initial
return root;
}
if (first != null)
{

//When first subtree contains result
return first;
}

// return the result of second subtree
return second;
}
else
{

//When tree node are empty [null]
return null;
}
}
//This function are handle the request of find LCA of two tree nodes
find_lca(node1, node2)
{
process.stdout.write("\nNodes [" + node1 + ", " + node2 + "] ");
var result = this.lca(this.root, node1, node2);
if (result != null)
{
process.stdout.write(" LCA : " + result.data + "\n");
}
else
{
process.stdout.write("Pair are missing \n");
}
}
}

function main()
{
//Make object of Binary Tree
var obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
*/
//Binary tree nodes
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.left.left = new Node(4);
obj.root.left.left.right = new Node(7);
obj.root.right.right.left = new Node(8);
//test case
obj.find_lca(8, 5);
obj.find_lca(7, 2);
obj.find_lca(7, 8);
obj.find_lca(3, 7);
obj.find_lca(5, 5);
obj.find_lca(4, 5);
}
main();``````

#### Output

``````Nodes [8, 5]  LCA : 3

Nodes [7, 2]  LCA : 2

Nodes [7, 8]  LCA : 1

Nodes [3, 7]  LCA : 1

Nodes [5, 5]  LCA : 5

Nodes [4, 5]  LCA : 1``````
``````# Python 3 Program
# Lowest common ancestor in a binary tree

# Class of Binary Tree Node
class Node :

# Make a tree TreeNode
def __init__(self, value) :
# Assign field values
self.data = value
self.left = None
self.right = None

class BinaryTree :

def __init__(self) :
# Set initial values
self.root = None

# This function are finding the LCA of given two  node
def lca(self, root, node1, node2) :
if (root != None) :
if (root.data == node1 or root.data == node2) :

# When tree node data is equal to node1 or value node2
return root

# here first and second variable are contain the information of
# left and right subtree when it is contain the given value
first = self.lca(root.left, node1, node2)
second = self.lca(root.right, node1, node2)
if (first != None and second != None) :

# When first and second subtree contains node values
# This condition is based on post order traversal so current node is resultant of LCA initial
return root

if (first != None) :

# When first subtree contains result
return first

#  return the result of second subtree
return second
else :

# When tree node are empty [null]
return None

# This function are handle the request of find LCA of two tree nodes
def find_lca(self, node1, node2) :
print("\nNodes [", node1 ,", ", node2 ,"] ", end = "")
result = self.lca(self.root, node1, node2)
if (result != None) :
print(" LCA : ", result.data ,"\n", end = "")
else :
print("Pair are missing \n", end = "")

def main() :
# Make object of Binary Tree
obj = BinaryTree()
#  Make A Binary Tree
#         -----------------------
#                 1
#                /  \
#               2    3
#              /    /  \
#             4    5    6
#              \       /
#               7     8
#

# Binary tree nodes
obj.root = Node(1)
obj.root.left = Node(2)
obj.root.right = Node(3)
obj.root.right.right = Node(6)
obj.root.right.left = Node(5)
obj.root.left.left = Node(4)
obj.root.left.left.right = Node(7)
obj.root.right.right.left = Node(8)
# test case
obj.find_lca(8, 5)
obj.find_lca(7, 2)
obj.find_lca(7, 8)
obj.find_lca(3, 7)
obj.find_lca(5, 5)
obj.find_lca(4, 5)

if __name__ == "__main__": main()``````

#### Output

``````Nodes [ 8 ,  5 ]  LCA :  3

Nodes [ 7 ,  2 ]  LCA :  2

Nodes [ 7 ,  8 ]  LCA :  1

Nodes [ 3 ,  7 ]  LCA :  1

Nodes [ 5 ,  5 ]  LCA :  5

Nodes [ 4 ,  5 ]  LCA :  1``````
``````# Ruby Program
# Lowest common ancestor in a binary tree

# Class of Binary Tree Node
class Node

# Define the accessor and reader of class Node
attr_accessor :data, :left, :right

# Make a tree TreeNode
def initialize(value)

# Assign field values
@data = value
@left = nil
@right = nil
end
end
class BinaryTree

# Define the accessor and reader of class BinaryTree
attr_accessor :root

def initialize()

# Set initial values
@root = nil
end
# This function are finding the LCA of given two  node
def lca(root, node1, node2)

if (root != nil)

if (root.data == node1 || root.data == node2)

# When tree node data is equal to node1 or value node2
return root
end
# here first and second variable are contain the information of
# left and right subtree when it is contain the given value
first = self.lca(root.left, node1, node2)
second = self.lca(root.right, node1, node2)
if (first != nil && second != nil)

# When first and second subtree contains node values
# This condition is based on post order traversal so current node is resultant of LCA initial
return root
end
if (first != nil)
# When first subtree contains result
return first
end

#  return the result of second subtree
return second
else

# When tree node are empty [null]
return nil
end
end
# This function are handle the request of find LCA of two tree nodes
def find_lca(node1, node2)

# Display node value
print("\nNodes [", node1 ,", ", node2 ,"] ")
result = self.lca(@root, node1, node2)
if (result != nil)

print(" LCA : ", result.data ,"\n")
else

print("Pair are missing \n")
end
end
end
def main()

# Make object of Binary Tree
obj = BinaryTree.new()
#  Make A Binary Tree
#         -----------------------
#                 1
#                /  \
#               2    3
#              /    /  \
#             4    5    6
#              \       /
#               7     8
#

# Binary tree nodes
obj.root = Node.new(1)
obj.root.left = Node.new(2)
obj.root.right = Node.new(3)
obj.root.right.right = Node.new(6)
obj.root.right.left = Node.new(5)
obj.root.left.left = Node.new(4)
obj.root.left.left.right = Node.new(7)
obj.root.right.right.left = Node.new(8)
# test case
obj.find_lca(8, 5)
obj.find_lca(7, 2)
obj.find_lca(7, 8)
obj.find_lca(3, 7)
obj.find_lca(5, 5)
obj.find_lca(4, 5)
end
main()``````

#### Output

``````Nodes [8, 5]  LCA : 3

Nodes [7, 2]  LCA : 2

Nodes [7, 8]  LCA : 1

Nodes [3, 7]  LCA : 1

Nodes [5, 5]  LCA : 5

Nodes [4, 5]  LCA : 1
``````
``````/*
Scala Program
Lowest common ancestor in a binary tree
*/
//Class of Binary Tree Node
class Node(var data: Int,
var left: Node,
var right: Node)
{
;
//Make a tree TreeNode
def this(value: Int)
{
//Assign field values
this(value,null,null);
}
}
class BinaryTree(var root: Node)
{
def this()
{
//Set initial values
this(null);
}
//This function are finding the LCA of given two  node
def lca(root: Node, node1: Int, node2: Int): Node = {
if (root != null)
{
if (root.data == node1 || root.data == node2)
{

//When tree node data is equal to node1 or value node2
return root;
}
//here first and second variable are contain the information of
//left and right subtree when it is contain the given value
var first: Node = lca(root.left, node1, node2);
var second: Node = lca(root.right, node1, node2);
if (first != null && second != null)
{

//When first and second subtree contains node values
//This condition is based on post order traversal so current node is resultant of LCA initial
return root;
}
if (first != null)
{

//When first subtree contains result
return first;
}

// return the result of second subtree
return second;
}
else
{

//When tree node are empty [null]
return null;
}
}
//This function are handle the request of find LCA of two tree nodes
def find_lca(node1: Int, node2: Int): Unit = {
//Display node value
print("\nNodes [" + node1 + ", " + node2 + "] ");
var result: Node = lca(root, node1, node2);
if (result != null)
{
print(" LCA : " + result.data + "\n");
}
else
{
print("Pair are missing \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Make object of Binary Tree
var obj: BinaryTree = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
*/
//Binary tree nodes
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.left.left = new Node(4);
obj.root.left.left.right = new Node(7);
obj.root.right.right.left = new Node(8);
//test case
obj.find_lca(8, 5);
obj.find_lca(7, 2);
obj.find_lca(7, 8);
obj.find_lca(3, 7);
obj.find_lca(5, 5);
obj.find_lca(4, 5);
}
}``````

#### Output

``````Nodes [8, 5]  LCA : 3

Nodes [7, 2]  LCA : 2

Nodes [7, 8]  LCA : 1

Nodes [3, 7]  LCA : 1

Nodes [5, 5]  LCA : 5

Nodes [4, 5]  LCA : 1``````
``````/*
Swift Program
Lowest common ancestor in a binary tree
*/
//Class of Binary Tree Node
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
//Make a tree TreeNode
init(_ value: Int)
{
//Assign field values
self.data = value;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: Node? ;
init()
{
//Set initial values
self.root = nil;
}
//This function are finding the LCA of given two  node
func lca(_ root: Node? , _ node1 : Int, _ node2: Int) -> Node?
{
if (root != nil)
{
if (root!.data == node1 || root!.data == node2)
{

//When tree node data is equal to node1 or value node2
return root;
}
//here first and second variable are contain the information of
//left and right subtree when it is contain the given value
let first: Node? = self.lca(root!.left, node1, node2);
let second: Node? = self.lca(root!.right, node1, node2);
if (first != nil && second != nil)
{

//When first and second subtree contains node values
//This condition is based on post order traversal so current node is resultant of LCA initial
return root;
}
if (first != nil)
{

//When first subtree contains result
return first;
}

// return the result of second subtree
return second;
}
else
{

//When tree node are empty [null]
return nil;
}
}
//This function are handle the request of find LCA of two tree nodes
func find_lca(_ node1: Int, _ node2: Int)
{
print("\nNodes [", node1 ,", ", node2 ,"] ", terminator: "");
let result: Node? = self.lca(self.root, node1, node2);
if (result != nil)
{
print(" LCA : ", result!.data ,"\n", terminator: "");
}
else
{
print("Pair are missing \n", terminator: "");
}
}
}
func main()
{
//Make object of Binary Tree
let obj: BinaryTree = BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
*/
//Binary tree nodes
obj.root = Node(1);
obj.root!.left = Node(2);
obj.root!.right = Node(3);
obj.root!.right!.right = Node(6);
obj.root!.right!.left = Node(5);
obj.root!.left!.left = Node(4);
obj.root!.left!.left!.right = Node(7);
obj.root!.right!.right!.left = Node(8);
//test case
obj.find_lca(8, 5);
obj.find_lca(7, 2);
obj.find_lca(7, 8);
obj.find_lca(3, 7);
obj.find_lca(5, 5);
obj.find_lca(4, 5);
}
main();``````

#### Output

``````Nodes [ 8 ,  5 ]  LCA :  3

Nodes [ 7 ,  2 ]  LCA :  2

Nodes [ 7 ,  8 ]  LCA :  1

Nodes [ 3 ,  7 ]  LCA :  1

Nodes [ 5 ,  5 ]  LCA :  5

Nodes [ 4 ,  5 ]  LCA :  1``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.