**Lowest Common Ancestor in BST** ===================================== **Problem Statement** ------------------- Given a binary search tree (BST) and two nodes in the tree, find the lowest common ancestor (LCA) of these two nodes. **Rules and Constraints** ------------------------ * The binary search tree is non-empty and has the following properties: + Each node has a unique integer key. + For any node, all keys in the left subtree are less than the key in the node. + For any node, all keys in the right subtree are greater than the key in the node. * The input nodes are guaranteed to be in the BST. * The time complexity of the solution should be O(h), where h is the height of the tree. * The space complexity of the solution should be O(1), excluding the space required for recursive call stack. * The solution should find the lowest common ancestor of the two input nodes, which is the node that is furthest from the root and is an ancestor of both nodes. **Input Description** ---------------------- * A binary search tree node with a key, a left child, and a right child. * Two nodes in the binary search tree. **Output Description** ---------------------- * The lowest common ancestor of the two input nodes in the binary search tree. ### Example **Input:** {"root":[6,2,8,0,4,7,9],"p":2,"q":8} **Output:** 6