Lowest common ancestor of a binary search tree

Given a binary search tree and two nodes node1 and node2, return lowest common ancestor value

Note: all node values are unique

Example 1

Input:        4   node1 = 4, node1 = 5
             / \
            2   5

Output: 4

Example 2

Input:        4   node1 = 2, node1 = 5
             / \
            2   5

Output: 4

/* Definition for TreeNode
public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
    }
}
*/
public class Solution
{
    public int LowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2)
    {
    }
}

All most all the time a solution or a hint on how to solve a problem can be found in the problem. For this problem, the hint is a binary search tree. Here's a definition of a binary search tree.

A Binary Search Tree (BST) is a binary tree where each node has a key and meet the following requirements:

• The left subtree of a node contains nodes with keys smaller then the node's key
• The right subtree of a node contains nodes with keys larger then the node's key
• The left and right subtrees are binary search trees

The lowest common ancestor(LCA) is defined between two nodes node1 and node2 as the lowest node in the tree that has both node1 and node2 as descendants and a node can be a descendant of itself.

 

 

For example, the lowest common ancestor (LCA) of nodes:

• LCA(5, 14) = 10
• LCA (7, 12) = 10
• LCA (5, 7) = 7
• LCA (12, 16) = 14
• LCA (1, 3) = -1

Approach:

• start traversing the tree from the root node
• if one of the nodes is greater than the root and another is less than the root then the root is the LCA
• if one of the nodes is the root node then the root node is the LCA
• if both nodes are smaller. The LCA on the left subtree
• if both nodes are greater. The LCA on the right subtree
• if the root node is null, it's mean all nodes were visited and LCA was not found. return -1

Code

    public int LowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2)
    {
        if (root == null)
        {
            return -1;
        }

        if (root.Value == node1.Value || root.Value == node2.Value)
        {
            return root.Value;
        }

        if (root.Value > node2.Value && root.Value > node1.Value)
        {
            return LowestCommonAncestor(root.Left, node1, node2);
        }

        if (root.Value < node2.Value && root.Value < node1.Value)
        {
            return LowestCommonAncestor(root.Right, node1, node2);
        }

        return root.Value;
    }

Time Complexity: O(n) where n is the number of nodes in the binary search tree.