Lowest Common Ancestor in a Binary Tree

Last Updated : 21 Jan, 2026

Given the root of a Binary Tree with unique values and two node values n1 and n2, find the Lowest Common Ancestor (LCA). LCA is the deepest node that has both n1 and n2 as descendants.

Note: Both node values are always present in the Binary Tree.

Examples:

Input: n1 .data= 4, n2.data = 5

420046698

Output: 2
Explanation: As shown below, LCA of 4 and 5 is 2.

420046699

Input: n1.data = 7, n2.data = 8

10

Output: 3
Explanation: As shown below, LCA of 7 and 8 is 3.

420046724
Try it on GfG Practice
redirect icon

Table of Content

[Naive Approach] Checking if each node is LCA - O(N^2) Time and O(h) space

The idea is to traverse the tree from root node, and for every node check if it is the LCA.
A node is the LCA if its left subtree has one target node and right subtree has the other target node.

C++ 
#include <iostream>
using namespace std;

// Node Structure
class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int value) {
        data = value;
        left = right = nullptr;
    }
};

// returns true if val is present 
// in the subtree of root
bool hasNode(Node* root, Node* node) {
    if (root == nullptr) return false;
    return (root == node) || 
            hasNode(root->left, node) || 
            hasNode(root->right, node);
}

Node* lca(Node* root, Node* n1, Node* n2) {
    if (root == nullptr) return nullptr;

    if (hasNode(root->left, n1) && hasNode(root->right, n2))
        return root;

    if (hasNode(root->left, n2) && hasNode(root->right, n1))
        return root;

    Node* lcaLeft = lca(root->left, n1, n2);
    Node* lcaRight = lca(root->right, n1, n2);

    return lcaLeft != nullptr ? lcaLeft : lcaRight;
}

int main() {
    // Create binary tree:
    //			   1
    //           /   \
    //          2     3
    //               / \
    //              6   7 
    //             /
    //            8

    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    root->right->left->left = new Node(8);

    // Node 7
    Node* n1 = root->right->right;

    // Node 8
    Node* n2 = root->right->left->left;

    Node* ans = lca(root, n1, n2);
    cout << ans->data << endl;
}
C 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Node Structure
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Create a new node
struct Node* newNode(int value) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// returns true if val is present 
// in the subtree of root
bool hasNode(struct Node* root, struct Node* node) {
    if (root == NULL) return false;
    return (root == node) || 
            hasNode(root->left, node) || 
            hasNode(root->right, node);
}

struct Node* lca(struct Node* root, struct Node* n1, struct Node* n2) {
    if (root == NULL) return NULL;

    if (hasNode(root->left, n1) && hasNode(root->right, n2))
        return root;

    if (hasNode(root->left, n2) && hasNode(root->right, n1))
        return root;

    struct Node* lcaLeft = lca(root->left, n1, n2);
    struct Node* lcaRight = lca(root->right, n1, n2);

    return (lcaLeft != NULL) ? lcaLeft : lcaRight;
}

int main() {
    // Create binary tree:
    //			   1
    //           /   \
    //          2     3
    //               / \
    //              6   7 
    //             /
    //            8

    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->right->left->left = newNode(8);

    // Node 7
    struct Node* n1 = root->right->right;

    // Node 8
    struct Node* n2 = root->right->left->left;


    struct Node* ans = lca(root, n1, n2);
    printf("%d\n", ans->data);
    
}
Java 
import java.util.ArrayList;
import java.util.List;

// Node Structure
class Node {
    int data;
    Node left, right;

    Node(int value) {
        data = value;
        left = right = null;
    }
}

class GFG {
    
    // returns true if val is present
    // in the subtree of root
    static boolean hasNode(Node root, Node node ) {
        if( root == null ) return false;
        
        return (root == node) || 
               hasNode(root.left, node) || 
               hasNode(root.right, node);
    }
    
    static Node lca(Node root, Node n1, Node n2) {
        if( root == null ) return null;
        
        if( hasNode(root.left, n1) && hasNode(root.right, n2)) 
            return root;
        
        if( hasNode(root.left, n2) && hasNode(root.right, n1)) 
            return root;
        
        Node lcaLeft = lca(root.left, n1, n2);
        Node lcaRight = lca(root.right, n1, n2);
        
        return lcaLeft != null ? lcaLeft : lcaRight;
        
    }

    public static void main(String[] args) {

        // Create binary tree:
        //			   1
        //           /   \
        //          2     3
        //               / \
        //              6   7 
        //             /
        //            8

        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.right.left.left = new Node(8);
        
        // Node 7
        Node n1 = root.right.right; 
        
        // Node 8
        Node n2 = root.right.left.left; 
        Node ans = lca(root, n1, n2);

        System.out.println(ans.data);
    }
}
Python 
# Node Structure
class Node:
    def __init__(self, value):
        self.data = value
        self.left = None
        self.right = None

# returns true if val is present 
# in the subtree of root
def hasNode(root, node):
    if root is None:
        return False
    return root == node or \
           hasNode(root.left, node) or \
           hasNode(root.right, node)

def lca(root, n1, n2):
    if root is None:
        return None

    if hasNode(root.left, n1) and hasNode(root.right, n2):
        return root
    if hasNode(root.left, n2) and hasNode(root.right, n1):
        return root

    lcaLeft = lca(root.left, n1, n2)
    lcaRight = lca(root.right, n1, n2)

    return lcaLeft if lcaLeft is not None else lcaRight

# Create binary tree:
#			   1
#           /   \
#          2     3
#               / \
#              6   7 
#             /
#            8

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.left = Node(8)

# Node 7
n1 = root.right.right

# Node 8
n2 = root.right.left.left

ans = lca(root, n1, n2)
print(ans.data)
C# 
using System;

class Node {
    public int data;
    public Node left, right;
    public Node(int value) {
        data = value;
        left = right = null;
    }
}

class GFG {

    // returns true if val is present 
    // in the subtree of root
    static bool hasNode(Node root, Node node) {
        if (root == null) return false;
        return (root == node) || 
                hasNode(root.left, node) || 
                hasNode(root.right, node);
    }

    static Node lca(Node root, Node n1, Node n2) {
        if (root == null) return null;

        if (hasNode(root.left, n1) && hasNode(root.right, n2)) return root;
        if (hasNode(root.left, n2) && hasNode(root.right, n1)) return root;

        Node lcaLeft = lca(root.left, n1, n2);
        Node lcaRight = lca(root.right, n1, n2);

        return lcaLeft != null ? lcaLeft : lcaRight;
    }

    public static void Main() {
        // Create binary tree:
        //			   1
        //           /   \
        //          2     3
        //               / \
        //              6   7 
        //             /
        //            8

        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.right.left.left = new Node(8);

        // Node 7
        Node n1 = root.right.right;

        // Node 8
        Node n2 = root.right.left.left;

        Node ans = lca(root, n1, n2);
        Console.WriteLine(ans.data);
    }
}
Javascript 
const Denque = require("denque");

// Node Structure
class Node {
    constructor(value) {
        this.data = value;
        this.left = null;
        this.right = null;
    }
}

// returns true if val is present in the subtree of root
function hasNode(root, node) {
    if (root === null) return false;
    return root === node || 
           hasNode(root.left, node) || 
           hasNode(root.right, node);
}

function lca(root, n1, n2) {
    if (root === null) return null;

    if (hasNode(root.left, n1) && hasNode(root.right, n2)) return root;
    if (hasNode(root.left, n2) && hasNode(root.right, n1)) return root;

    const lcaLeft = lca(root.left, n1, n2);
    const lcaRight = lca(root.right, n1, n2);

    return lcaLeft !== null ? lcaLeft : lcaRight;
}

// Create binary tree:
//			   1
//           /   \
//          2     3
//               / \
//              6   7 
//             /
//            8

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.right.left.left = new Node(8);

// Node 7
const n1 = root.right.right;

// Node 8
const n2 = root.right.left.left;

const ans = lca(root, n1, n2);
console.log(ans.data);

Output
3

[Better Approach] Storing Paths of Nodes from Root - O(n) Time and O(n) Space

The idea is to store the paths to the target nodes from the root in two separate arrays. Then start traversing from the 0th index and look simultaneously into the values stored in the arrays, the LCA is the last matching element in both the arrays.

420046724

Path from root to 7 = 1 -> 3-> 7
Path from root to 8 = 1 -> 3 -> 6 -> 8

  • We start checking from 0th index. As both of the values match, we move to the next index.
  • Now check for values at 1st index, they are also matching, so we move to the 2nd index.
  • Now, we check for 3rd index, there's a mismatch so we consider the previous value. 
  • Therefore, the LCA of (7, 8) is 3.
C++ 
#include <iostream>
#include <vector>
using namespace std;

// Node Structure
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int value) {
        data = value;
        left = right = nullptr;
    }
};

// Finds the path from root to given node
bool findPath(Node* root, vector<Node*>& path, Node* n) {
    if (root == nullptr) return false;

    // Store current node
    path.push_back(root);

    if (root == n || findPath(root->left, path, n) || findPath(root->right, path, n)) {
        return true;
    }

    // remove root from path and return false
    path.pop_back();
    return false;
}

Node* lca(Node* root, Node* n1, Node* n2) {
    vector<Node*> path1, path2;

    // Find paths from root to n1 
    // and root to n2
    if (!findPath(root, path1, n1) || !findPath(root, path2, n2)) return nullptr;

    // Compare the paths to get 
    // the first different value
    int i = 0;
    for (i = 0; i < path1.size() && i < path2.size(); i++) {
        if (path1[i] != path2[i]) return path1[i - 1];
    }
    return path1[i - 1];
}

int main() {
    // Create binary tree:
    //			   1
    //           /   \
    //          2     3
    //               / \
    //              6   7
    //             /
    //            8

    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    root->right->left->left = new Node(8);

    Node* n1 = root->right->right;
    Node* n2 = root->right->left->left;

    Node* ans = lca(root, n1, n2);
    if (ans) cout << ans->data << endl;
}
C 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Node Structure
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Create new node
struct Node* newNode(int value) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = value;
    node->left = node->right = NULL;
    return node;
}

// Finds the path from root to given node
bool findPath(struct Node* root, struct Node** path, int* pathLen, struct Node* n) {
    if (root == NULL) return false;

    // Store current node
    path[(*pathLen)++] = root;

    if (root == n || findPath(root->left, path, pathLen, n) || findPath(root->right, path, pathLen, n))
        return true;

    // remove root from path and return false
    (*pathLen)--;
    return false;
}

struct Node* lca(struct Node* root, struct Node* n1, struct Node* n2) {
    struct Node* path1[100]; int len1 = 0;
    struct Node* path2[100]; int len2 = 0;

    // Find paths from root to n1
    // and root to n2.
    if (!findPath(root, path1, &len1, n1) || !findPath(root, path2, &len2, n2))
        return NULL;

    // Compare the paths to get the first
    // different value
    int i = 0;
    for (i = 0; i < len1 && i < len2; i++) {
        if (path1[i] != path2[i]) return path1[i-1];
    }
    return path1[i-1];
}

int main() {
    // Create binary tree:
    //			   1
    //           /   \
    //          2     3
    //               / \
    //              6   7
    //             /
    //            8

    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->right->left->left = newNode(8);

    struct Node* n1 = root->right->right;
    struct Node* n2 = root->right->left->left;

    struct Node* ans = lca(root, n1, n2);
    if (ans != NULL)
        printf("%d\n", ans->data);
}
Java 
import java.util.ArrayList;
import java.util.List;

// Node Structure
class Node {
    int data;
    Node left, right;

    Node(int value) {
        data = value;
        left = right = null;
    }
}

class GFG {

    static Node lca(Node root, Node n1, Node n2) {

        List<Node> path1 = new ArrayList<>();
        List<Node> path2 = new ArrayList<>();

        // Find paths from root to n1
        // and root to n2.
        if(!findPath(root, path1, n1) ||
                !findPath(root, path2, n2))
            return null;

        // Compare the paths to get the first
        // different value
        int i = 0;
        for(i = 0; i<path1.size() && i<path2.size(); i++) {
            if(path1.get(i) != path2.get(i))
                return path1.get(i-1);
        }

        return path1.get(i-1);
    }

    // Finds the path from root to given node
    static boolean findPath(Node root, List<Node> path, Node n) {

        if (root == null) {
            return false;
        }

        // Store current node
        path.add(root);

        if (root == n ||
                findPath(root.left, path, n) ||
                findPath(root.right, path, n)) {
            return true;
        }

        // remove root from path and return false
        path.remove(path.size() - 1);

        return false;
    }

    public static void main(String[] args) {

        // Create binary tree:
        //			   1
        //           /   \
        //          2     3
        //               / \
        //              6   7
        //             /
        //            8

        Node root = new Node(1);
        root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.right.left.left = new Node(8);

        Node n1 = root.right.right;
        Node n2 = root.right.left.left;

        Node ans = lca(root, n1, n2);

        System.out.println(ans.data);
    }
}
Python 
# Node Structure
class Node:
    def __init__(self, value):
        self.data = value
        self.left = None
        self.right = None

# Finds the path from root to given node
def findPath(root, path, n):
    if root is None:
        return False

    # Store current node
    path.append(root)

    if root == n or findPath(root.left, path, n) or findPath(root.right, path, n):
        return True

    # remove root from path and return false
    path.pop()
    return False

def lca(root, n1, n2):
    path1 = []
    path2 = []

    # Find paths from root to n1 
    # and root to n2
    if not findPath(root, path1, n1) or not findPath(root, path2, n2):
        return None

    # Compare the paths to get 
    # the first different value
    i = 0
    while i < len(path1) and i < len(path2):
        if path1[i] != path2[i]:
            return path1[i-1]
        i += 1

    return path1[i-1]

# Create binary tree:
#			   1
#           /   \
#          2     3
#               / \
#              6   7
#             /
#            8

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.left = Node(8)

n1 = root.right.right
n2 = root.right.left.left

ans = lca(root, n1, n2)
print(ans.data)
C# 
using System;
using System.Collections.Generic;

// Node structure
class Node {
    public int data;
    public Node left, right;
    public Node(int value) {
        data = value;
        left = right = null;
    }
}

class GFG {

    static Node lca(Node root, Node n1, Node n2) {
        List<Node> path1 = new List<Node>();
        List<Node> path2 = new List<Node>();

        // Find paths from root to n1 
        // and root to n2.
        if (!findPath(root, path1, n1) || !findPath(root, path2, n2))
            return null;

        // Compare the paths to 
        // get the first different value
        int i = 0;
        for (i = 0; i < path1.Count && i < path2.Count; i++) {
            if (path1[i] != path2[i])
                return path1[i - 1];
        }
        return path1[i - 1];
    }

    // Finds the path from root to given node
    static bool findPath(Node root, List<Node> path, Node n) {
        if (root == null) return false;

        // Store current node
        path.Add(root);

        if (root == n || findPath(root.left, path, n) || findPath(root.right, path, n))
            return true;

        // remove root from path and return false
        path.RemoveAt(path.Count - 1);
        return false;
    }

    public static void Main() {
        // Create binary tree:
        //			   1
        //           /   \
        //          2     3
        //               / \
        //              6   7
        //             /
        //            8

        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.right.left.left = new Node(8);

        Node n1 = root.right.right;
        Node n2 = root.right.left.left;

        Node ans = lca(root, n1, n2);
        Console.WriteLine(ans.data);
    }
}
Javascript 
const Denque = require("denque");

// Node Structure
class Node {
    constructor(value) {
        this.data = value;
        this.left = null;
        this.right = null;
    }
}

// Finds the path from root to given node
function findPath(root, path, n) {
    if (root === null) return false;

    // Store current node
    path.push(root);

    if (root === n || findPath(root.left, path, n) || findPath(root.right, path, n)) {
        return true;
    }

    // remove root from path and return false
    path.pop();
    return false;
}

function lca(root, n1, n2) {
    const path1 = [];
    const path2 = [];

    // Find paths from root to n1 
    // and root to n2
    if (!findPath(root, path1, n1) || !findPath(root, path2, n2)) return null;

    // Compare the paths to 
    // get the first different value
    let i =0;
    for (i = 0; i < path1.length && i < path2.length; i++) {
        if (path1[i] !== path2[i]) return path1[i - 1];
    }
    return path1[i - 1];
}

// Create binary tree:
//			   1
//           /   \
//          2     3
//               / \
//              6   7
//             /
//            8

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.right.left.left = new Node(8);

const n1 = root.right.right;
const n2 = root.right.left.left;

const ans = lca(root, n1, n2);
console.log(ans.data);

Output
3

[Expected Approach] Using Single Traversal

In this approach, we start with the root node and recursively searches for the given nodes n1 and n2. If the current root is null, it returns null. If the root matches either of the keys, it returns the root as a potential LCA. Then, it recursively checks the left and right subtrees. If both the left and right recursive calls return non-null values, it means one key is in the left subtree and the other is in the right subtree, so the current root is the LCA. If only one subtree contains the keys, the recursive call returns the non-null subtree result as the LCA.

C++ 
#include <iostream>
using namespace std;

// Node Structure
class Node {
public:
    Node *left, *right;
    int data;
    Node(int k) {
        data = k;
        left = nullptr;
        right = nullptr;
    }
};

Node* lca(Node* root, Node* n1, Node* n2) {

    if (!root)
        return nullptr;

    // If either key matches with root data, return root
    if (root == n1 || root == n2)
        return root;

    Node* leftLca = lca(root->left, n1, n2);
    Node* rightLca = lca(root->right, n1, n2);

    // If both of the above calls return Non-NULL, then one
    // data 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 if left subtree or 
    // right subtree is LCA
    return leftLca ? leftLca : rightLca;
}

int main() {

    // Create binary tree:
    //			   1
    //           /   \
    //          2     3
    //               / \
    //              6   7 
    //             /
    //            8

    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    root->right->left->left = new Node(8);

    Node* n1 = root->right->right;
    Node* n2 = root->right->left->left;

    Node* ans = lca(root, n1, n2);
    cout<<ans->data;

    return 0;
}
C 
#include <stdio.h>
#include <stdlib.h>

// Node Structure
struct Node {
    struct Node *left, *right;
    int key;
};


struct Node* lca(struct Node* root, struct Node* n1, struct Node* n2) {
    if (root == NULL)
        return NULL;

    // If either key matches with root data, return root
    if (root == n1 || root == n2)
        return root;

    struct Node* leftLca = lca(root->left, n1, n2);
    struct Node* rightLca = lca(root->right, n1, n2);

    // If both of the above calls return Non-NULL, then one
    // key is present in once subtree and other is present
    // in other, so this node is the LCA
    if (leftLca && rightLca)
        return root;

    // Otherwise check if left subtree or 
    // right subtree is LCA
    return (leftLca != NULL) ? leftLca : rightLca;
}

struct Node* createnode(int key) {
    struct Node* newnode = 
      	(struct Node*)malloc(sizeof(struct Node));
    newnode->key = key;
    newnode->left = newnode->right = NULL;
    return newnode;
}

int main() {

    // construct the binary tree
    //			   1
    //           /   \
    //          2     3
    //         / \   / \
    //        4  5  6   7 
    //             /
    //            8
    struct Node* root = createnode(1);
    root->left = createnode(2);
    root->right = createnode(3);
    root->right->left = createnode(6);
    root->right->right = createnode(7);
    root->right->left->left = createnode(8);
    
    struct Node* n1 = root->right->right;
    struct Node* n2 = root->right->left->left;

    struct Node* ans = lca(root, n1, n2);

    printf("%d", ans->key);

    return 0;
}
Java 
// Node Structure
class Node {
    Node left, right;
    int data;

    Node(int k) {
        data = k;
        left = null;
        right = null;
    }
}

class GFG {
    static Node lca(Node root, Node n1, Node n2) {

        if (root == null)
            return null;

        // If either key matches with root data, return root
        if (root == n1 || root == n2)
            return root;

        Node leftLca = lca(root.left, n1, n2);
        Node rightLca = lca(root.right, n1, n2);

        // If both of the above calls return Non-NULL, then one
        // node is present in one subtree and the other is present
        // in the other, so this node is the LCA
        if (leftLca != null && rightLca != null)
            return root;

        // Otherwise check if left subtree or 
        // right subtree is LCA
        return (leftLca != null) ? leftLca : rightLca;
    }

    public static void main(String[] args) {

        // Create binary tree:
        //			   1
        //           /   \
        //          2     3
        //               / \
        //              6   7 
        //             /
        //            8

        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.right.left.left = new Node(8);

        Node n1 = root.right.right;
        Node n2 = root.right.left.left;

        Node ans = lca(root, n1, n2);

        System.out.println(ans.data);
    }
}
Python 
# Node Structure
class Node:
    def __init__(self, k):
        self.data = k
        self.left = None
        self.right = None

def lca(root, n1, n2):

    if not root:
        return None

    # If either key matches with root data, return root
    if root == n1 or root == n2:
        return root

    leftLca = lca(root.left, n1, n2)
    rightLca = lca(root.right, n1, n2)

    # If both of the above calls return Non-NULL, then one
    # data is present in one subtree and the other is present
    # in the other, so this node is the LCA
    if leftLca and rightLca:
        return root

    # Otherwise check if left subtree or 
    # right subtree is LCA
    return leftLca if leftLca else rightLca

if __name__ == "__main__":

    #  Create binary tree:
    # 			   1
    #            /   \
    #           2     3
    #                / \
    #               6   7 
    #              /
    #             8

    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.right.left = Node(6)
    root.right.right = Node(7)
    root.right.left.left = Node(8)

    n1 = root.right.right;
    n2 = root.right.left.left;

    ans = lca(root, n1, n2);

    print(ans.data)
C# 
using System;

// Node Structure
class Node {
    public Node left, right;
    public int data;

    public Node(int k) {
        data = k;
        left = null;
        right = null;
    }
}

class GFG {
    static Node lca(Node root, Node n1, Node n2) {

        if (root == null)
            return null;

        // If either key matches with root data, return root
        if (root == n1 || root == n2)
            return root;

        Node leftLca = lca(root.left, n1, n2);
        Node rightLca = lca(root.right, n1, n2);

        // If both of the above calls return Non-NULL, then one
        // data is present in one subtree and the other is present
        // in the other, so this node is the LCA
        if (leftLca != null && rightLca != null)
            return root;

        // Otherwise check if left subtree or 
        // right subtree is LCA
        return leftLca != null ? leftLca : rightLca;
    }

    static void Main() {

        // Create binary tree:
        //			   1
        //           /   \
        //          2     3
        //               / \
        //              6   7 
        //             /
        //            8

        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.right.left.left = new Node(8);

        Node n1 = root.right.right;
        Node n2 = root.right.left.left;

        Node ans = lca(root, n1, n2);

        Console.WriteLine(ans.data);
    }
}
JavaScript 
// Node Structure
class Node {
    constructor(k) {
        this.left = null;
        this.right = null;
        this.data = k;
    }
}

function lca(root, n1, n2) {

    if (root === null)
        return null;

    // If either key matches with root data, return root
    if (root === n1 || root === n2)
        return root;

    let leftLca = lca(root.left, n1, n2);
    let rightLca = lca(root.right, n1, n2);

    // If both of the above calls return Non-NULL, then one
    // data 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 if left subtree or 
    // right subtree is LCA
    return leftLca ? leftLca : rightLca;
}


// Create binary tree:
//			   1
//           /   \
//          2     3
//               / \
//              6   7 
//             /
//            8

let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.right.left.left = new Node(8);

let n1 = root.right.right;
let n2 = root.right.left.left;

let ans = lca(root, n1, n2);

console.log(ans.data);

Output
3

Time Complexity: O(n)
Auxiliary Space: O(h), where h is the height of the tree.

Comment

Explore