Amobee Interview Questions

You are given a binary tree of unique positive numbers. Each node in the binary tree is represented as a dictionary with the following keys:

• data: integer value stored in the node
• left: reference to the left child (or None)
• right: reference to the right child (or None)

node = {
    "data": 6,
    "left": {
        "data": 3,
        "left": {...},
        "right": {...}
    },
    "right": {
        "data": 9,
        "left": {...},
        "right": {...}
    }
}

Given two node values as input (value1 and value2), write a function to return the value of the nearest common ancestor (lowest node in the tree that has both nodes as descendants).

Note: If one of the nodes doesn’t exist in the tree, return -1.

Example:

Input:

# Diagram of the binary tree
'''
      6        
     / \        
    3   9     
   / \
  2   11
     / \
    5   8
'''
value1 = 8
value2 = 2

Output:

common_ancestor(root,value1,value2) -> 3

Explanation:

• Ancestors of 8: 11 → 3 → 6
• Ancestors of 2: 3 → 6
• Common ancestors: 3 and 6
• The nearest common ancestor is 3.