Lowest Common Ancestor (Hard)
Good morning! Here's our prompt for today.
You may see this problem at Facebook, Adobe, Lyft, Zillow, Two Sigma, Goldman Sachs, Uipath, Airtable, Veeam, Seagate, and New Relic.
In the official React documentation, it's recommended that to find out where state data should live, the following steps be taken:
- Identify every component that renders something based on that state.
- Find a common owner component (a single component above all the components that need the state in the hierarchy).
- Either the common owner or another component higher up in the hierarchy should own the state.
This is an algorithmic problem-- let's find the lowest common ancestor!
You're given a binary search tree tree1 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.
1/*
2 7
3 / \
4 4 8
5 / \
6 1 5
7*/The method will called in the following manner: lowestCommonAncestor(root, node1, node2);.
You can assume our standard node definition for the tree vertices:
1// Node definition
2function Node(val) {
3 this.val = val;
4 this.left = this.right = null;
5}Bonus: is there a way to find the lowest common ancestor of two nodes if the root wasn't passed as a parameter?
Constraints
- Number of nodes in the BST <=
1000 - The nodes will always contain integer values between
-1000000000and1000000000 - Expected time complexity :
O(n) - Expected space complexity :
O(1)
xxxxxxxxxxvar assert = require('assert');function lowestCommonAncestor(root, node1, node2) { // Fill in this method return root;}function Node(val) { this.val = val; this.left = null; this.right = null;}// Regular binary treesvar tree1 = new Node(4);tree1.left = new Node(1);tree1.right = new Node(3);var tree2 = new Node(5);tree2.left = new Node(10);tree2.left.left = new Node(17);tree2.left.right = new Node(3);tree2.right = new Node(8);// Binary search treesvar tree3 = new Node(6);tree3.left = new Node(3);