Lowest Common Ancestor of a Binary Search Tree
Similar Problems:
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Github: code.dennyzhang.com
Credits To: leetcode.com
Leave me comments, if you have better ways to solve.
## Blog link: https://code.dennyzhang.com/lowest-common-ancestor-of-a-binary-search-tree ## Basic Ideas: For BST, get min(p.val, q.val) and max(p.val, q.val) ## Check from the root node ## If both are smaller than root.val, move the left sub-tree ## If both are bigger than root.val, move the right-tree ## If one smaller and one bigger, the current node is what we want ## Assumption: No duplicate value in the BST ## Complexity: Time O(k), Space O(1). k is the height # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ stack = [] r = root min_val = min(p.val, q.val) max_val = max(p.val, q.val) while r and (r.val > max_val or r.val < min_val): if r.val > max_val: r = r.left else: r = r.right return r
Share It, If You Like It.