LeetCode: Lowest Common Ancestor of a Binary Search Tree Solution
Recursive approachApproach
Properties of a BST (grabbed from leetcode.com):
- Left subtree of a node N contains nodes whose values are lesser than or equal to node N's value.
- Right subtree of a node N contains nodes whose values are greater than node N's value.
- Both left and right subtrees are also BSTs.
From that, we see that the way is:
- find the first node (go from root) that satisfy the condition of a BST (left <= target node <= right)
- if 2 given nodes values are greater than the iterated node, go right
- if 2 given nodes values are smaller than the iterated node, go left
Implementation (recursive)
1/**2 * Definition for a binary tree node.3 * function TreeNode(val) {4 * this.val = val;5 * this.left = this.right = null;6 * }7 */89/**10 * @param {TreeNode} root11 * @param {TreeNode} p12 * @param {TreeNode} q13 * @return {TreeNode}14 */15var lowestCommonAncestor = function (root, p, q) {16 if (17 (root.val >= p.val && root.val <= q.val) ||18 (root.val <= p.val && root.val >= q.val)19 ) {20 return root21 } else if (root.val > p.val && root.val > q.val) {22 return lowestCommonAncestor(root.left, p, q)23 } else if (root.val < p.val && root.val < q.val) {24 return lowestCommonAncestor(root.right, p, q)25 }26}
Implementation (iterative)
1var lowestCommonAncestor = function (root, p, q) {2 while (root) {3 if (p.val < root.val && q.val < root.val) {4 root = root.left5 } else if (p.val > root.val && q.val > root.val) {6 root = root.right7 } else {8 break9 }10 }1112 return root13}
References
Comments
Loading comments...
Tags
leetcode
tree
Apply and earn a $2,500 bonus once you're hired on your first job!
Clients from the Fortune 500 to Silicon Valley startups
Choose your own rate, get paid on time
From hourly, part-time, to full-time positions
Flexible remote working environment
A lot of open JavaScript jobs!!
Fact corner: Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.
Still hesitate? Read HoningJS author's guide on dealing with Toptal interview process.