ALGODAILY

April 15, 2021

On two occasions I have been asked, ‘Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?’ I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question.”

- Charles Babbage

---

Day 9: Lowest Common Ancestor

You're given a binary search tree and two of its child nodes as parameters. Can you write a method lowestCommonAncestor(root: Node, node1: Node, node2: Node) to identify the lowest common ancestor of the two nodes? The lowest common ancestor is the deepest node that has both of the two nodes as descendants.

In the below example, the lowest common ancestor of node 5 and 8 is 7.

/*
       7
      / \
     4   8
    / \
   1   5
*/

The method will called in the following manner: lowestCommonAncestor(root, node1, node2);.

You can assume our standard node definition for the tree vertices:

function Node(val) {
  this.val = val;
  this.left = this.right = null;
}

Constraints

• Number of nodes in the BST <= 1000
• The nodes will always contain integer values between -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(1)

Get the Solution →

Have you seen this question before? We are frequently adding problems and may have updated the order. You can change the day that you're on in the settings panel. As always, you can see the solution and a full step by step explanation at this link.

---

Our technical interview course gets results. Love the daily emails? AlgoDaily exists to provide hand-held coding interview coaching and career resources to developers from non-traditional paths. In the course, you'll find:

• LIFETIME access to the full guided interview course with over 150 hours of interview prep material (a $399+ value - use it again and again throughout your career)
• PDF, Mobi, and ePub copies of the 732 page ebook The AlgoDaily Book: Core Essentials! (a $29 value)
• Access to 500+ clear, intuitive illustrations and visualizations to help you understand hard concepts instantly
• Hundreds of plain English, introductory interactive tutorials and lessons on data structures, algorithms, and interview patterns
• Hundreds of in-depth solution tutorials with interactive, executable code snippets walked through our CTPBO method
• Access to a growing premium video solutions collection. 8+ hours of tutorials and helpful explanations to unblock you in no time (a $99 value)
• Access to an exclusive jobs application tracking tool (usually $10/month)
• Restart the AlgoDaily newsletter challenges from any day
• Acess to all problem solutions submitted by the community
• New material on interview techniques, career success, and breaking into software added weekly
• ON SALE: All of the above, $215+ sharply discounted for LIFETIME access

Become An Affiliate

If you're a fan of AlgoDaily.com and would like to share the love, we want to reward you! If you run an app, community, blog, or simply have lots of friends interested in the course-- get yourself a nice side revenue stream. Sign up to be an affiliate of algodaily.com. Affiliates get a whopping 50% commission on subscriptions referred.

How does it work? Sign up here, and start sharing your link. When people make a purchase on AlgoDaily.com, you'll accrue 50% of the purchase price. Affiliates get paid out on month end.

---

One last thing-- if you liked this email, and found value in it, could you kindly forward it to a friend who might benefit?

Our mission is to make tough technical interviews accessible to all, especially those from non-traditional CS backgrounds. I'd deeply appreciate your help in spreading the word!

Thanks,
Jake