Lowest Common Ancestor of a Binary Search Tree

  • Amazon Interview Questions
  • Facebook Interview Questions
  • Linkedin Interview Questions
  • Microsoft Interview Questions

Lowest Common Ancestor of a Binary Search Tree Link

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

        /   \
       3     6
      / \   / \
     0   8 5   7
        / \
       1   9


Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 3, q = 6

Output: 7

Explanation: The LCA of nodes 6 and 3 is 7.


  • All of the nodes’ values will be unique.
  • p and q are different and both values will exist in the BST.


This is the problem given only to check your basic understanding of BST. First we go through the basic points on BST:

  1. Left subtree of a node N contains nodes whose values are lesser than or equal to node N’s value.
  2. Right subtree of a node N contains nodes whose values are greater than node N’s value.
  3. Both left and right subtrees are also BSTs.

These basic understanding is the logic behind it’s implementation:



public static class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {
            return root;
        if ((root.val - p.val) * (root.val - q.val) > 0) {
            if (root.val - p.val > 0) {
                return lowestCommonAncestor(root.left, p, q);
            return lowestCommonAncestor(root.right, p, q);
        return root;

Complexity Analysis:

  • Time Complexity: O(n).
  • Space Complexity: O(n).
Scroll to Top

Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]