## Tuesday, May 17, 2022

### Easy_Question15 : Lowest Common Ancestor in a Binary Search Tree

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).”

Example 1:

```Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.```

Example 2:

```Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.```

Example 3:

```Input: root = [2,1], p = 2, q = 1
Output: 2```

``````class Node
{
int data;
Node left, right;

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

class BinaryTree
{
Node root;

/* Function to find LCA of n1 and n2.
The function assumes that both
n1 and n2 are present in BST */
static Node lca(Node root, int n1, int n2)
{
while (root != null)
{
// If both n1 and n2 are smaller
// than root, then LCA lies in left
if (root.data > n1 &&
root.data > n2)
root = root.left;

// If both n1 and n2 are greater
// than root, then LCA lies in right
else if (root.data < n1 &&
root.data < n2)
root = root.right;

else break;
}
return root;
}

/* Driver program to test lca() */
public static void main(String args[])
{
// Let us construct the BST shown in the above figure
BinaryTree tree = new BinaryTree();
tree.root = new Node(20);
tree.root.left = new Node(8);
tree.root.right = new Node(22);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(12);
tree.root.left.right.left = new Node(10);
tree.root.left.right.right = new Node(14);

int n1 = 10, n2 = 14;
Node t = tree.lca(tree.root, n1, n2);
System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);

n1 = 14;
n2 = 8;
t = tree.lca(tree.root, n1, n2);
System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);

n1 = 10;
n2 = 22;
t = tree.lca(tree.root, n1, n2);
System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);

}
}``````

Output
```LCA of 10 and 14 is 12
LCA of 14 and 8 is 8
LCA of 10 and 22 is 20 ```

Complexity Analysis:

• Time Complexity: O(h).
The Time Complexity of the above solution is O(h), where h is the height of the tree.
• Space Complexity: O(1).
The space complexity of the above solution is constant.

## You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS