LeetCode: Lowest Common Ancestor of a Binary Search Tree Posted on January 15, 2018July 26, 2020 by braindenny Lowest Common Ancestor of a Binary Search Tree Similar Problems: Lowest Common Ancestor of a Binary Tree CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #binarytree, #lca 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. // https://code.dennyzhang.com/lowest-common-ancestor-of-a-binary-search-tree // Basic Ideas: // // Complexity: Time O(log(n)), Space O(1) /** * Definition for TreeNode. * type TreeNode struct { * Val int * Left *ListNode * Right *ListNode * } */ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { if root == nil { return root } if p.Val > q.Val { p, q = q, p } res := root for res != nil { if res == p || res == q { return res } if res.Val > p.Val && res.Val < q.Val { return res } if res.Val > q.Val { res = res.Left } else { res = res.Right } } return res } // https://code.dennyzhang.com/lowest-common-ancestor-of-a-binary-search-tree // Basic Ideas: // // Complexity: Time O(log(n)), Space O(1) /** * Definition for TreeNode. * type TreeNode struct { * Val int * Left *ListNode * Right *ListNode * } */ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { res := root for res != nil { if res.Val > p.Val && res.Val > q.Val { res = res.Left } else { if res.Val < p.Val && res.Val < q.Val { res = res.Right } else { return res } } } return res } // https://code.dennyzhang.com/lowest-common-ancestor-of-a-binary-search-tree // Basic Ideas: recursive // // Complexity: Time O(log(n)), Space O(1) /** * Definition for TreeNode. * type TreeNode struct { * Val int * Left *ListNode * Right *ListNode * } */ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { if root == nil || root == p || root == q { return root } if p.Val > q.Val { p, q = q, p } if root.Val > p.Val && root.Val < q.Val { return root } else { if root.Val > q.Val { return lowestCommonAncestor(root.Left, p, q) } else { return lowestCommonAncestor(root.Right, p, q) } } } ## 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(log(n))), Space O(1) # 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 Post Views: 5