Question
Binary Search Tree is given. BST is a tree structure that the value of every parent's nodes is greater than the left child node and less than the right child node. Also, two Tree nodes that are included in the BST are provided as an argument that named p and q. You need to find the lowest ancestor of those given tree node.
Solution
You should travel from the top node to the child until you find the p or q node. Or until the current node is greater than one of child and less than another. If finding, return the current node. when both are less than the current one, go down left. Otherwise, go down right. You will be able to find the target for sure.
Submission
Here is the result of the above solution.
Runtime: 84 ms, faster than 32.49% of Python3 online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 17.8 MB, less than 5.55% of Python3 online submissions for Lowest Common Ancestor of a Binary Search Tree.
Time complexity: O(logN)
Space complexity: O(1)
The given tree must be a BST tree node. So, the time complexity is gonna be O(logN) in worst case because we can skip a half of tree node when both are greater or less than a current node.
This is my python code
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root is None:
return None
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
