Lowest Common Ancestor of a Binary Search Tree

Find the lowest common ancestor of the binary search tree.

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Approach

Java

public class LCABST {
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(6);
        tree.left = new TreeNode(2);
        TreeNode p = tree.left;
        tree.right = new TreeNode(8);
        TreeNode q = tree.right;
        tree.left.left = new TreeNode(0);
        tree.left.right = new TreeNode(4);
        tree.right.left = new TreeNode(7);
        tree.right.right = new TreeNode(9);
        tree.left.right.left = new TreeNode(3);
        tree.left.right.right = new TreeNode(5);
        TreeNode incres = lowestCommonAncestor(tree, p, q);
        System.out.println(incres.val);
    }

    // function to find the lowest common
    // ancestor of the binary search tree
    private static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p,
                                             TreeNode q) {

        // base case if root is NULL
        if (root == null)
            return null;

        // base case
        if (p.val >= root.val && q.val <= root.val)
            return root;

        // base case
        if (p.val <= root.val && q.val >= root.val)
            return root;
        else {

            // call for left subtree
            if (p.val < root.val && q.val < root.val)
                return lowestCommonAncestor(root.left, p, q);

            // call for right subtree
            else
                return lowestCommonAncestor(root.right, p, q);
        }
    }
}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode() {
	}

	TreeNode(int val) {
		this.val = val;
	}

	TreeNode(int val, TreeNode left, TreeNode right) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};

//function to find the lowest common
//ancestor of the binary search tree
TreeNode* lowestCommonAncestor(TreeNode* root, 
             TreeNode* p, TreeNode* q) 
{
       //base case if root is NULL
        if(root==NULL)
              return NULL;

        //base case
        if(p->data>=root->data&&q->data<=root->data)
                return root;
        
        //base case
        if(p->data<=root->data&&q->data>=root->data)
               return root;
        else
        {

            //call for left subtree
            if(p->data<root->data &&q->data<root->data)
             return lowestCommonAncestor(root->left,p,q);

             //call for right subtree
            else
                return lowestCommonAncestor(root->right,p,q);
        }
}
int main()
{
    TreeNode *tree=new TreeNode(6);
    tree->left=new TreeNode(2);
    TreeNode *p=tree->left;
    tree->right=new TreeNode(8);
    TreeNode *q=tree->right;
    tree->left->left=new TreeNode(0);
    tree->left->right=new TreeNode(4);
    tree->right->left=new TreeNode(7);
    tree->right->right=new TreeNode(9);
    tree->left->right->left=new TreeNode(3);
    tree->left->right->right=new TreeNode(5);
    TreeNode *LCA=lowestCommonAncestor(tree,p,q);
    cout<<LCA->data<<"\n";
    
    return 0;
}