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.