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.

Lowest common ancestor in a binary tree

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) {
        //means both side are node start and end not found
        //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) {
          //means both side are node start and last not found
          //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) {
                    //means both side are node start and last not found
                    //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_reader :data, :left, :right
    attr_accessor :data, :left, :right
    def initialize(value) 
        @data = value
        @left = @right = nil
    end
end

class BinaryTree 
    attr_reader :root
    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_reader :data, :left, :right
    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_reader :root
    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.

New Comment







© 2021, kalkicode.com, All rights reserved