Lowest Common Ancestor in BST
Properties and Validation DSA practice problem on Onlearn.
Difficulty: medium.
Topics: What is the Lowest Common Ancestor (LCA) in a Binary Search Tree (BST), and how can it be efficiently determined?, Binary Search Tree, Binary Tree, Time Complexity, Space Complexity, Recursion, Iteration, Pointer, Algorithm, tree algorithms, binary search tree properties, divide and conquer, binary search tree, tree traversal, BST Properties, Algorithmic Paradigms.
Lowest Common Ancestor of a Binary Search Tree Given a Binary Search Tree (BST), find the lowest common ancestor (LCA) of two given nodes, p and q, 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).” It is guaranteed that both p and q exist in the BST. Input The input consists of: The root of a Binary Search Tree. Two integer values, p val and q val, representing the values of the two nodes p and q for which to find the LCA. Output Return the value of the lowest common ancestor (LCA) node. Constraints The number of nodes in the tree is in the range [2, 10^5]. 10^9 <= Node.val <= 10^9 All Node.val are unique. p val != q val p val and q val exist in the BST. Example Test Cases Example 1: Input: (The tree represented by the array is: root=6, left=2, right=8, 2's left=0, 2's right=4, 8's left=7, 8's right=9, 4's left=3, 4's right=5) Output: Explanation: The LCA of nodes with values 2 and 8 is 6. Example 2: Input: Output: Explanation: The LCA of nodes with values 2 and 4 is 2. Node 4 is a descendant of node 2.