Closest Common Ancestor in Binary Tree
Log in to access the full course (free for 2024!)
Given two values in a binary tree, write a function findClosestAncestor
that finds the closest ancestor node relative to these target nodes.
You will be given a root
as the input along with the values of two nodes that exist in the tree.
The tree contains only unique integers, and the child values will always be different.
It's important to note that this is a binary tree and not a BST where the value of the node could indicate its position as an ancestor or where to search for the children.
9
/ \
5 4
/ \ \
1 7 3
/ \ \
42 10 2
findClosestAncestor(root, 10, 7); // 5
The tree nodes will use the following implementation:
class BinaryNode {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
Breakdown
Validate My Answer
This can be solved iteratively or recursively. Let's go ahead and assume you don't need to worry about stack overflows if you're interested in solving it recursively. That's the solution I'll be showing.
A node can be the common ancestor with itself and a child node.
At worst, the root is the common ancestor for all nodes.
This can be solved in O(n) time and space.
Test Results
Run your code and see results here...
Closest Common Ancestor in Binary Tree
xxxxxxxxxx
/**
* @param {BinaryNode} root
* @param {int} firstChildValue
* @param {int} secondChildValue
* @return {BinaryNode}
*/
const findClosestAncestor = (root, firstChildValue, secondChildValue) => {
// Your solution here
}
Given two values in a binary tree, write a function findClosestAncestor
that finds the closest ancestor node relative to these target nodes.
You will be given a root
as the input along with the values of two nodes that exist in the tree.
The tree contains only unique integers, and the child values will always be different.
It's important to note that this is a binary tree and not a BST where the value of the node could indicate its position as an ancestor or where to search for the children.
9
/ \
5 4
/ \ \
1 7 3
/ \ \
42 10 2
findClosestAncestor(root, 10, 7); // 5
The tree nodes will use the following implementation:
class BinaryNode {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}