distance BT cpp

// program to print the distance between 2 nodes in a binary tree
#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;
}

// function to find and return the level of a node in binary tree
int level_of_node(node* root, int data, int level = -1){
    // if the tree is empty or if we reach a leaf node then return 0
    if (root == NULL){
        return -1;
    }
    if(root->data == data){
        return level+1;
    }

    // check in the left subtree for the element
    // if found then return the level
    int level_node = level_of_node(root->left, data, level + 1);
    if (level_node != -1){
        return level_node;
    }

    // searching for the node in right subtree
    level_node = level_of_node(root->right, data, level + 1);
    return level_node;

}

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);
}

// function that returns the distance between 2 given nodes
int distance_between(node* root, int a, int b){
    node* LCA = least_common_ancestor(root, a, b);
    return level_of_node(LCA, a) + level_of_node(LCA, b);
}

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<<"Distance between nodes 6 and 10 is : "<<distance_between(head, 6, 10)<<endl;
    cout<<"Distance between nodes 1 and 10 is : "<<distance_between(head, 1, 10)<<endl;
    cout<<"Distance between nodes 11 and 10 is : "<<distance_between(head, 11, 10)<<endl;

}


/*

Distance between nodes 6 and 10 is : 7
Distance between nodes 1 and 10 is : 5
Distance between nodes 11 and 10 is : 9

Process finished with exit code 0

*/