LCA cpp

#include <iostream>
using namespace std;

// node class
class node{
public:
    int data;
    node* left;
    node* right;
};

// function that returns a pointer to new node
node* createNode(int element){
    node* temp = (node*) malloc(sizeof(node));
    temp->data = element;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

node* least_common_ancestor(node* root, int n1, int n2){
    if(root == NULL){
        return root;
    }

    if(root->data == n1 || root->data == n2){
        return root;
    }

    node* left = least_common_ancestor(root->left, n1, n2);
    node* right = least_common_ancestor(root->right, n1, n2);

    if(left != NULL && right != NULL){
        return root;
    }

    if(left != NULL){
        return least_common_ancestor(root->left, n1, n2);
    }
    return least_common_ancestor(root->right, n1, n2);
}


int main() {

    node* head = createNode(1);
    head->left = createNode(2);
    head->right = createNode(3);
    head->left->left = createNode(4);
    head->left->right = createNode(5);
    head->right->right = createNode(6);
    head->left->left->right = createNode(7);
    head->right->right->left = createNode(8);
    head->left->left->right->left = createNode(9);
    head->left->left->right->left->left = createNode(10);
    head->right->right->left->right = createNode(11);
    cout<<"Least common Ancestor of nodes 6 and 10 is : "<<least_common_ancestor(head, 6, 10)->data<<endl;
    cout<<"Least common Ancestor of nodes 4 and 5 is : "<<least_common_ancestor(head, 4, 5)->data<<endl;
    cout<<"Least common Ancestor of nodes 5 and 10 is : "<<least_common_ancestor(head, 5, 10)->data<<endl;

}



/*

Least common Ancestor of nodes 6 and 10 is : 1
Least common Ancestor of nodes 4 and 5 is : 2
Least common Ancestor of nodes 5 and 10 is : 2
Process finished with exit code 0

*/