# 235. Lowest Common Ancestor of a Binary Search Tree

Reference: LeetCode EPI 14.4
Difficulty: Easy

## Problem

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

Note:

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

Example:

## Analysis

Methods:

1. Recursion
• Start traversing the tree from the root node.
• If both the nodes p and q are in the right subtree, then continue the search with right subtree.
• Same for left subtree.
• If above steps are not true, it means that we have found the node which is common to node p‘s and q‘s subtrees.
• Better code:

Time: $O(h)$
Space: $O(h)$

1. Iteration
• Use $O(1)$ space.

Time: $O(h)$
Space: $O(1)$

Comment
Junhao Wang
a software engineering cat