Find the Lowest Common Ancestor in a Binary Search Tree

June 23, 2019

Please write your own version of program in the comment section below in different languages. Best answer will be uploaded on the website page once, the page is ready

One comment on “Find the Lowest Common Ancestor in a Binary Search Tree”


  • Zubair

    package com.company;

    import java.io.*;
    import java.lang.*;
    import java.util.*;

    public class Main {
    public static void main(String[] args) {
    abc tree =new abc();
    tree.add(8);
    tree.add(3);
    tree.add(6);
    tree.add(10);
    tree.add(4);
    tree.add(7);
    tree.add(1);
    tree.add(14);
    tree.add(13);
    node l =tree.lca(6,1, tree.root);
    if (l!=null){
    System.out.println(l.data);
    }
    }
    }
    class node {
    int data;
    node left;
    node right;

    public node(int data) {
    this.data = data;
    this.left=null;
    this.right=null;
    }
    }
    class abc{
    public node root=null;
    public node insert(node node ,int value){
    if (node==null){
    return new node(value);
    }
    else if (valuenode.data){
    node.right=insert(node.right,value);
    }
    return node;
    }
    public void add(int value){
    root =insert(root,value);
    }
    public boolean checkbst(node node){
    if (node==null){
    return true;
    }
    if (node.left!=null&&node.left.data>node.data){
    return false;
    }
    if (node.right!=null&&node.right.data<node.data){
    return false;
    }
    return true;
    }
    public node lca(int n1 ,int n2 ,node node){
    if (node==null){
    return null;
    }
    else if (n1<node.data&&n2node.data&&n1>node.data){
    return lca(n1,n2,node.right);
    }
    else {
    return node;
    }
    }
    }