BSTLCA - Editorial

editorial
1

Prerequisites :- Binary Search Trees, BT traversals, LCA in Binary tree.

Problem :- Given a binary search tree, and two nodes values X and Y, find the LCA (lowest common ancestor) of these two nodes.

Solution Approach :- The solution utilizes the properties of a binary search tree to efficiently find the Lowest Common Ancestor of two given nodes. The key observation is that the LCA will be a node where one node lies in the left subtree, and the other lies in the right subtree.

Algorithm:

    1. Start from the root.
    1. If both nodes X and Y are greater than the current node’s value, move to the right subtree.
    1. If both nodes X and Y are smaller than the current node’s value, move to the left subtree.
    1. If neither of the above conditions is true, it means one node lies in the left subtree, and the other lies in the right subtree, so the current node is the LCA.
    1. Return the LCA.

Time Complexity: O(N), because in the worst case, the algorithm visits all the nodes in the given BST.

Space complexity: O(1), because only constant space (for few variables) is used.