Given a binary search tree (BST) and two node values p and q, return the value of their lowest common ancestor. Use the BST property — at any node, if both p and q are less than node.val, descend left; if both are greater, descend right; otherwise the node is the LCA.
[2, 10⁴].-10⁹ ≤ Node.val ≤ 10⁹Node.val are unique.p ≠ qp and q will exist in the tree.Use BST ordering rather than the general LCA recursion.
An ancestor of a node is any node on the way down from the root to it, the node itself included. The lowest common ancestor of p and q is the deepest node that is on both of those ways down.
Time O(h)Space O(1)
The full walkthrough and code are part of Premium
6