{"id":710,"date":"2024-10-19T13:53:00","date_gmt":"2024-10-19T08:23:00","guid":{"rendered":"https:\/\/codexplained.in\/?p=710"},"modified":"2025-11-24T15:33:04","modified_gmt":"2025-11-24T10:03:04","slug":"find-lowest-common-ancestor-in-binary-tree","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=710","title":{"rendered":"Find Lowest Common Ancestor in Binary Tree"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n\n\/\/ A binary tree node has data, a pointer to the left child, and a pointer to the right child.\nstruct Node {\n    int data;\n    struct Node* left;\n    struct Node* right;\n};\n\n\/\/ Utility function to create a new node.\nstruct Node* newNode(int data) {\n    struct Node* node = (struct Node*)malloc(sizeof(struct Node));\n    node->data = data;\n    node->left = NULL;\n    node->right = NULL;\n    return node;\n}\n\n\/\/ Function to find the LCA of two given nodes n1 and n2.\nstruct Node* findLCA(struct Node* root, int n1, int n2) {\n    \/\/ Base case: If the root is NULL, return NULL.\n    if (root == NULL) {\n        return NULL;\n    }\n\n    \/\/ If either n1 or n2 matches with root's data, return the root.\n    if (root->data == n1 || root->data == n2) {\n        return root;\n    }\n\n    \/\/ Look for keys in the left and right subtrees.\n    struct Node* leftLCA = findLCA(root->left, n1, n2);\n    struct Node* rightLCA = findLCA(root->right, n1, n2);\n\n    \/\/ If both leftLCA and rightLCA are non-NULL, then one key is present in one subtree\n    \/\/ and the other is present in the other. So, this node is the LCA.\n    if (leftLCA && rightLCA) {\n        return root;\n    }\n\n    \/\/ Otherwise, check which side has a non-NULL value and return it.\n    return (leftLCA != NULL) ? leftLCA : rightLCA;\n}\n\nint main() {\n    \/\/ Let's create the example binary tree mentioned above.\n    struct Node* root = newNode(3);\n    root->left = newNode(5);\n    root->right = newNode(1);\n    root->left->left = newNode(6);\n    root->left->right = newNode(2);\n    root->right->left = newNode(0);\n    root->right->right = newNode(8);\n    root->left->right->left = newNode(7);\n    root->left->right->right = newNode(4);\n\n    int n1 = 5, n2 = 1;\n    struct Node* lca = findLCA(root, n1, n2);\n\n    if (lca != NULL) {\n        printf("LCA of %d and %d is %d\\n", n1, n2, lca->data);\n    } else {\n        printf("LCA of %d and %d does not exist.\\n", n1, n2);\n    }\n\n    n1 = 6, n2 = 4;\n    lca = findLCA(root, n1, n2);\n\n    if (lca != NULL) {\n        printf("LCA of %d and %d is %d\\n", n1, n2, lca->data);\n    } else {\n        printf("LCA of %d and %d does not exist.\\n", n1, n2);\n    }\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
Output Explanation<\/h2>\n\n\n\n
The program creates a binary tree as shown above and finds the LCA of different pairs of nodes:<\/p>\n\n\n\n
Output<\/p>\n\n\n\n
LCA of 5 and 1 is 3\nLCA of 6 and 4 is 5\n<\/code><\/pre>\n\n\n\n
    \n
  • For nodes 5 and 1<\/strong>: The LCA is 3<\/code>, as 3<\/code> is the first common ancestor node for both.<\/li>\n\n\n\n
  • For nodes 6 and 4<\/strong>: The LCA is 5<\/code>, since 6<\/code> and 4<\/code> are both descendants of node 5<\/code>.<\/li>\n<\/ul>\n\n\n\n
    How It Works<\/h2>\n\n\n\n
      \n
    1. The function findLCA<\/code> is called with the root<\/code> node and the values n1<\/code> and n2<\/code>.<\/li>\n\n\n\n
    2. It checks if the current node matches either n1<\/code> or n2<\/code>.<\/li>\n\n\n\n
    3. If not, it recursively searches both the left and right subtrees.<\/li>\n\n\n\n
    4. If one node is found in the left subtree and the other in the right, the current node is the LCA.<\/li>\n\n\n\n
    5. If both nodes are in the same subtree, that subtree’s root becomes the LCA.<\/li>\n<\/ol>\n