Katkat
Back

Find cheapest common ancestor in a tree

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to navigate tree structures and perform post-order traversal to identify an ancestor node based on a custom aggregate criterion (the minimum value).

Problem: Lowest Price Common Ancestor

You are given a binary tree where each node contains an integer value representing the price of an item. Given two target nodes p and q, find the common ancestor that has the minimum value among all common ancestors of p and q.

Function Signature

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def find_cheapest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:

Constraints

  • The tree contains at least two nodes.
  • All node.val are unique positive integers.
  • p and q are guaranteed to exist in the tree.

Example

Input:

  • Tree: [10 (root), 5 (left), 20 (right), 2 (left-left), 8 (left-right)]
  • Targets: p = 2, q = 8
  • Common ancestors: 5 (value 5) and 10 (value 10).
  • Output: 5 (because 5 < 10).

Edge Cases

  • One target node is a direct descendant of the other.
  • The root is the only common ancestor.
  • The tree is a skewed line.

Hints

Hint 1

First, identify all common ancestors of the two nodes; a node is a common ancestor if p and q are both in its subtree (or one is the node itself).

Hint 2

Perform a post-order traversal to pass information upward: return the state of whether p, q, or both have been found in the current subtree.

Hint 3

During the traversal, whenever the current node is identified as a common ancestor, compare its value against a global or stored variable tracking the minimum value seen so far among common ancestors.

Follow-up questions

  • How would your approach change if the tree was an n-ary tree rather than a binary tree?
  • What is the time and space complexity of your solution, and can you optimize the space if the tree depth is skewed?
  • If the tree were updated frequently with new prices, how would you maintain this information efficiently?