Lowest Common Ancestor Of A Binary Search Tree

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root->val > p->val && root->val > q->val) {
            return lowestCommonAncestor(root->left, p, q);
        } else if (root->val < p->val && root->val < q->val) {
            return lowestCommonAncestor(root->right, p, q);
        } else {
            return root;
        }
    }
};

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return root;
        }
    }
}

                                            
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root->val > p->val && root->val > q->val)
        return lowestCommonAncestor(root->left, p, q);
    else if (root->val < p->val && root->val < q->val)
        return lowestCommonAncestor(root->right, p, q);
    else
        return root;
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) {
            return LowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            return LowestCommonAncestor(root.right, p, q);
        } else {
            return root;
        }
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
var lowestCommonAncestor = function(root, p, q) {
    if ((root.val - p.val) * (root.val - q.val) <= 0) return root;
    return lowestCommonAncestor(root.val < p.val ? root.right : root.left, p, q);
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    if (!root || root === p || root === q) {
        return root;
    }
    
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    
    if (left && right) {
        return root;
    }
    
    return left || right;
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @param TreeNode $p
     * @param TreeNode $q
     * @return TreeNode
     */
    function lowestCommonAncestor($root, $p, $q) {
        if ($root->val < $p->val && $root->val < $q->val) {
            return $this->lowestCommonAncestor($root->right, $p, $q);
        } elseif ($root->val > $p->val && $root->val > $q->val) {
            return $this->lowestCommonAncestor($root->left, $p, $q);
        } else {
            return $root;
        }
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */

class Solution {
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        var ancestor: TreeNode? = root
        while true {
            if p!.val < ancestor!.val && q!.val < ancestor!.val {
                ancestor = ancestor!.left
            } else if p!.val > ancestor!.val && q!.val > ancestor!.val {
                ancestor = ancestor!.right
            } else {
                return ancestor
            }
        }
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root.Val > p.Val && root.Val > q.Val {
        return lowestCommonAncestor(root.Left, p, q)
    } else if root.Val < p.Val && root.Val < q.Val {
        return lowestCommonAncestor(root.Right, p, q)
    } else {
        return root
    }
}

                                            
class TreeNode
    attr_accessor :val, :left, :right
    def initialize(val)
        @val = val
        @left = nil
        @right = nil
    end
end

def lowest_common_ancestor(root, p, q)
    return root if root.val == p.val || root.val == q.val
    
    if root.val > p.val && root.val > q.val
        return lowest_common_ancestor(root.left, p, q)
    elsif root.val < p.val && root.val < q.val
        return lowest_common_ancestor(root.right, p, q)
    else
        return root
    end
end

To solve this coding challenge, we need to find the Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree (BST). In a BST, for each node, the value of its left subtree nodes will be lesser, and the value of its right subtree nodes will be greater than the node's value. This property of the BST can be leveraged to efficiently determine the LCA of two given nodes.

# Explanation

Definition Recap :

The Lowest Common Ancestor (LCA) of two nodes \( p \) and \( q \) in a binary tree is the lowest node that has both \( p \) and \( q \) as descendants, including the node itself.

Understanding the Binary Search Tree (BST) :

For a given node \( n \),
n.left

contains nodes with values less than
n.val

, and
n.right

contains nodes with values greater than
n.val

.

LCA Property and BST Characteristics :

Given nodes \( p \) and \( q \):

If both \( p \) and \( q \) are less than \( n \), then the LCA must be in the left subtree of \( n \).
If both \( p \) and \( q \) are greater than \( n \), then the LCA must be in the right subtree of \( n \).
If one is less than \( n \) and the other is greater than \( n \), or one of them is equal to \( n \), then \( n \) is the LCA.

Algorithm :

Start with the root of the tree.
Traverse the tree:

If both nodes are smaller than the current node, move to the left child.
If both nodes are larger than the current node, move to the right child.
If the nodes diverge (one on the left and one on the right) or if one of them equals the current node, the current node is the LCA.

# Detailed Steps in Pseudocode

Initial Setup :

Start at the root node of the BST.

Traversal Logic :

While the current node is not null:

Compare the values of \( p \), \( q \) with the current node's value.
Decide whether to move left, move right, or return the current node as the LCA.

Return the Result :

The result is the node where the paths to \( p \) and \( q \) diverge or where one of the nodes equals the current node.

# Pseudocode with Comments

                                            
# Define the function to find the Lowest Common Ancestor in a BST
function FindLowestCommonAncestor(root, node_p, node_q):
# Start with the root of the tree
current_node = root

# Traverse the tree until we find the LCA or reach a null node
while current_node is not null:
# If both p and q are smaller than the current node's value, go left
if node_p.value < current_node.value and node_q.value < current_node.value:
current_node = current_node.left

# If both p and q are greater than the current node's value, go right
elif node_p.value > current_node.value and node_q.value > current_node.value:
current_node = current_node.right

# If p and q diverge or one of them equals the current node's value, return the current node as LCA
else:
return current_node

# If we exit the loop without finding the LCA, return null (though per constraints, this should not happen)
return null

# Step-by-Step Explanation of the Pseudocode

Initialization :

Assign the
root

of the tree to the variable
current_node

for traversal.

Loop until LCA is Found or Reaching Null :

Check if both
node_p

and
node_q

have values less than
current_node.value

. If true, move to the left child (
current_node.left

).
Check if both
node_p

and
node_q

have values greater than
current_node.value

. If true, move to the right child (
current_node.right

).
If neither condition is met, then either:

One node lies on the left and the other on the right, making
current_node

the LCA.
One node equals
current_node

, making
current_node

the LCA as per the definition it allows the node to be a descendant of itself.

Returning the Result :

The LCA is found at the point where the paths to
node_p

and
node_q

diverge, or at a point where one of the nodes is the
current_node

.

This approach ensures that the LCA is found efficiently by leveraging the properties of the BST, making the traversal nearly logarithmic in nature, i.e., \( O(\log n) \) on average, where \( n \) is the number of nodes in the tree.