Interview Query

Nearest Common Ancestor

1
Have you seen this question before?

You are given a binary tree of unique positive numbers. Each node in the tree is implemented as a Node class object with the attributes Node.left and Node.right, indicating the node’s left and right neighbors, respectively, and Node.data that hold an integer value.

class Node():
        def __init__(self, value):
            self.data = value
            self.left = None
            self.right = None

Given two nodes as input (value1 and value2), write a function to return the value of the nearest node that is a parent to both nodes.

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

As the parents for the nodes 8 and 2 are the root node 6 and the node 3. 3 is the nearest parent that has the two nodes as children.

Next question: Audio Chat Success
.....
Python 3.9.6
Loading editor
Use Shift + Enter to run code