Find Lowest Common Ancestor in Binary Tree

#include <stdio.h>
#include <stdlib.h>

// A binary tree node has data, a pointer to the left child, and a pointer to the right child.
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Utility function to create a new node.
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Function to find the LCA of two given nodes n1 and n2.
struct Node* findLCA(struct Node* root, int n1, int n2) {
    // Base case: If the root is NULL, return NULL.
    if (root == NULL) {
        return NULL;
    }

    // If either n1 or n2 matches with root's data, return the root.
    if (root->data == n1 || root->data == n2) {
        return root;
    }

    // Look for keys in the left and right subtrees.
    struct Node* leftLCA = findLCA(root->left, n1, n2);
    struct Node* rightLCA = findLCA(root->right, n1, n2);

    // If both leftLCA and rightLCA are non-NULL, then one key is present in one subtree
    // and the other is present in the other. So, this node is the LCA.
    if (leftLCA && rightLCA) {
        return root;
    }

    // Otherwise, check which side has a non-NULL value and return it.
    return (leftLCA != NULL) ? leftLCA : rightLCA;
}

int main() {
    // Let's create the example binary tree mentioned above.
    struct Node* root = newNode(3);
    root->left = newNode(5);
    root->right = newNode(1);
    root->left->left = newNode(6);
    root->left->right = newNode(2);
    root->right->left = newNode(0);
    root->right->right = newNode(8);
    root->left->right->left = newNode(7);
    root->left->right->right = newNode(4);

    int n1 = 5, n2 = 1;
    struct Node* lca = findLCA(root, n1, n2);

    if (lca != NULL) {
        printf("LCA of %d and %d is %d\n", n1, n2, lca->data);
    } else {
        printf("LCA of %d and %d does not exist.\n", n1, n2);
    }

    n1 = 6, n2 = 4;
    lca = findLCA(root, n1, n2);

    if (lca != NULL) {
        printf("LCA of %d and %d is %d\n", n1, n2, lca->data);
    } else {
        printf("LCA of %d and %d does not exist.\n", n1, n2);
    }

    return 0;
}