Lowest Common Ancestor of a Binary Search Tree

Lowest Common Ancestor

On this page we will se how to find Lowest Common Ancestor of a Binary Search Tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself). Thus LCA is guaranteed to exist if both the nodes are present in tree.  In any other case it is NULL.

Sum of all Nodes of a binary tree

Sum of all Nodes in a Binary Tree

Algorithm :

  • Create a recursive function that takes a node, as well as two values n1 and n2.
  • If the value of the current node is less than both n1 and n2, it means that the lowest common ancestor (LCA) lies in the right subtree. Call the recursive function for the right subtree.
  • If the value of the current node is greater than both n1 and n2, it means that the LCA lies in the left subtree. Call the recursive function for the left subtree.
  • If both of the above cases are false, it means that the current node is the LCA. Return the current node as the LCA.
Lowest Common Ancestor in Binary tree

To find LCA , The below code assumes that both the nodes are present in the tree. To extend this algorithm for the cases that , it works even if only one of nodes are present in the tree, is left as an exercise to the reader.  There are 2 ways to do this – One is to check beforehand if the nodes are present in the tree or not. Other way to change our solution a bit to account to check if both the nodes are present. Like 2 variables which update when we find the nodes in finding LCA.

Code to find Lowest Common Ancestor in a binary tree in Java

Run
//Java implementation to find lowest common ancestor of
// n1 and n2 using one traversal of binary tree

/* Class containing left and right child of current
node and key value*/
class Node {
    int data;
    Node left, right;

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

class BTree {

    Node root;

    // This function returns pointer to LCA of two given
    // values n1 and n2. This function assumes that n1 and
    // n2 are present in Binary Tree
    Node LCA(Node node, int val1, int val2) {
        // Base case
        if (node == null)
            return null;

        // If either n1 or n2 matches with root's key, return root. Note this assumes that
        // both thr roots are present in the tree. To extend this algo for those cases , which
        //account if either of the node is present or not, is Left as an exercise for students.
        if (node.data == val1 || node.data == val2)
            return node;

        // Look for keys in left and right subtrees
        Node left_lca = LCA(node.left, val1, val2);
        Node right_lca = LCA(node.right, val1, val2);

        // If both the left_lca and right_lca is not null, that means this is LCA.
        if (left_lca != null && right_lca != null)
            return node;

        // Otherwise check if left subtree or right subtree is LCA
        if (left_lca != null)
            return left_lca;
        else
            return right_lca;

    }
}
public class Main{
    public static void main(String args[]) {
        BTree tree = new BTree();
        tree.root = new Node(11);
        tree.root.left = new Node(9);
        tree.root.right = new Node(8);
        tree.root.left.left = new Node(7);
        tree.root.left.right = new Node(6);
        tree.root.right.left = new Node(5);
        tree.root.right.right = new Node(4);
        System.out.println("LCA(9, 8) = " +
            tree.LCA(tree.root, 9, 8).data);

        System.out.println("LCA(11, 4) = " +
            tree.LCA(tree.root, 11, 4).data);

    }
}

Output

LCA(9, 8) = 11
LCA(11, 4) = 11

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Introduction to Trees

Binary Trees

Binary Search Trees

Traversals

  • Traversal in Trees
  • Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
  • Tree Traversals: Depth First Search (DFS) : C | C++ | Java
  • Construct a Binary Tree from Postorder and Inorder

B – Trees

AVL Trees

  • AVL Trees
    • AVL Trees: Introduction
    • AVL Tree Insertion : C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

  • Depth First Traversals – C | C++ | Java
  • Level Order Traversal – C | C++Java
  • Construct Tree from given Inorder and Preorder traversals – C | C++Java
  • Construct Tree from given Postorder and Inorder traversals – C | C++Java
  • Construct Tree from given Postorder and Preorder traversal – C | C++Java
  • Find size of the Binary tree – C | C++Java
  • Find the height of binary tree – C | C++Java
  • Find maximum in binary tree – C | C++Java
  • Check whether two tree are identical- CC++Java
  • Spiral Order traversal of Tree- CC++Java
  • Level Order Traversal Line by Line – C | C++Java
  • Hand shaking lemma and some Impotant Tree Properties.
  • Check If binary tree if Foldable or not.- CC++Java
  • check whether tree is Symmetric – C| C++Java.
  • Check for Children-Sum in Binary Tree- C|C++Java
  • Sum of all nodes in Binary Tree- CC++ | Java
  • Lowest Common Ancestor in Binary Tree- CC++ | Java

Introduction to Trees

Binary Trees

Binary Search Trees

Traversals

  • Traversal in Trees
  • Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
  • Tree Traversals: Depth First Search (DFS) : C | C++ | Java
  • Construct a Binary Tree from Postorder and Inorder

B – Trees

AVL Trees

  • AVL Trees
    • AVL Trees: Introduction
    • AVL Tree Insertion :  C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

  • Depth First Traversals – C | C++ | Java
  • Level Order Traversal – C | C++Java
  • Construct Tree from given Inorder and Preorder traversals – C | C++Java
  • Construct Tree from given Postorder and Inorder traversals – C | C++Java
  • Construct Tree from given Postorder and Preorder traversal – C | C++Java
  • Find size of the Binary tree – C | C++Java
  • Find the height of binary tree – C | C++Java
  • Find maximum in binary tree – C | C++Java
  • Check whether two tree are identical- CC++Java
  • Spiral Order traversal of Tree- CC++Java
  • Level Order Traversal LIne by Line – C | C++Java
  • Hand shaking lemma and some Impotant Tree Properties.
  • Check If binary tree if Foldable or not.- CC++Java
  • check whether tree is Symmetric  C| C++Java.
  • Check for Children-Sum in Binary Tree- C|C++Java
  • Sum of all nodes in Binary Tree- CC++ | Java
  • Lowest Common Ancestor in Binary Tree. CC++ | Java