Amazon Interview Question
SDE1sCountry: Hong Kong
c# solution:
public class Employee
{
public int Id { get; set; }
public string Name { get; set; }
public List<Employee> Reports { get; set; }
}
public static Employee ClosestCommonManager(Employee ceo, Employee firstEmployee, Employee secondEmployee)
{
Employee currentClosestManager = ceo;
if (!Covers(ceo, firstEmployee) || !Covers(ceo, secondEmployee))
return null;
Queue q = new Queue();
q.Enqueue(ceo);
while (!q.IsEmpty())
{
var emp =(Employee) q.Dequeue();
if (emp != null)
{
foreach (var employee in emp.Reports)
{
if (Covers(employee, firstEmployee) && Covers(employee, secondEmployee)
&& (employee.Id != firstEmployee.Id && employee.Id != secondEmployee.Id))
{
currentClosestManager = employee;
q.Enqueue(employee);
}
}
}
}
return currentClosestManager;
}
public static bool Covers(Employee root, Employee p)
{
if (root == null)
return false;
if (root.Id == p.Id)
return true;
foreach (var employee in root.Reports)
{
if (Covers(employee, p))
{
return true;
}
}
return false;
}
//Driver program
public static void Test()
{
var bill = new Employee{Id = 1,Name = "Bill",Reports = new List<Employee>()};
var dom = new Employee { Id = 2, Name = "Dom",Reports = new List<Employee>() };
var samir = new Employee { Id = 3, Name = "Samir" ,Reports = new List<Employee>()};
var michael = new Employee { Id = 4, Name = "Michael",Reports = new List<Employee>() };
var bob = new Employee { Id = 5, Name = "Bob",Reports = new List<Employee>() };
var peter = new Employee { Id = 6, Name = "Peter",Reports = new List<Employee>() };
var porter = new Employee { Id = 7, Name = "Porter",Reports = new List<Employee>() };
var milton = new Employee { Id = 8, Name = "Milton",Reports = new List<Employee>() };
var nina = new Employee { Id = 9, Name = "Nina",Reports = new List<Employee>() };
peter.Reports.Add(milton);
peter.Reports.Add(nina);
dom.Reports.Add(bob);
dom.Reports.Add(peter);
dom.Reports.Add(porter);
bill.Reports.Add(dom);
bill.Reports.Add(samir);
bill.Reports.Add(michael);
var ccm = ClosestCommonManager(bill, milton, nina);
Console.WriteLine(ccm.Name);
ccm = ClosestCommonManager(bill, nina, porter);
Console.WriteLine(ccm.Name);
ccm = ClosestCommonManager(bill, nina, samir);
Console.WriteLine(ccm.Name);
ccm = ClosestCommonManager(bill, peter, nina);
Console.WriteLine(ccm.Name);
}
Lowest common ancestor direct application
Here is my implementation.
public class Employee {
private String name;
private List<Employee> reportee;
private Employee manager;
Employee(String name) {
this.name = name;
reportee = new ArrayList<>();
}
public void setManager(Employee m) {
manager = m;
}
public void addReprotee(Employee e) {
reportee.add(e);
e.manager = this;
}
//O(log(n)) time complexity, O(1) memory
static Employee closestCommonManager2(Employee a, Employee b) {
Employee e1 = a;
Employee e2 = b;
int h1 = 0;
int h2 = 0;
while (e1 != null || e2 != null) {
if (e1 != null) {
e1 = e1.manager ;
h1++;
}
if (e2 != null) {
e2 = e2.manager ;
h2++;
}
}
int diff = Math.abs(h1 - h2);
if(h1 > h2) {
e1 = a;
e2 = b;
} else {
e1 = b;
e2 = a;
}
while (diff > 0) {
e1 = e1.manager;
diff--;
}
while (e1 != e2) {
e1 = e1.manager ;
e2 = e2.manager ;
}
return e1;
}
//O(log(n)) time complexity, O(log(n)) memory
static Employee closestCommonManager(Employee a, Employee b) {
Stack<Employee> ls1 = new Stack<Employee>();
Stack<Employee> ls2 = new Stack<Employee>();
while (a != null || b != null) {
if (a != null) {
ls1.push(a);
a = a.manager ;
}
if (b != null) {
ls2.push(b);
b = b.manager;
}
}
while(!ls1.isEmpty() && !ls2.isEmpty()) {
if (ls1.peek() != ls2.peek()) {
break;
}
a = ls1.pop();
ls2.pop();
}
return a;
}
public String toString() {
return name;
}
}
private static Node lca(Node node, Node nodeA, Node nodeB) {
if (node == null)
return null;
if (node.data == nodeA.data || node.data == nodeB.data)
return node;
List<Node> children = node.chidren;
int count = 0;
Node lca = null;
for (Node n : children) {
Node tmpNode = lca(n, nodeA, nodeB);
if (tmpNode != null) {
lca = tmpNode;
count++;
}
}
if (count == 2) {
return node;
}
return lca;
}
private static Node lca(Node node, Node nodeA, Node nodeB) {
if (node == null)
return null;
if (node.data == nodeA.data || node.data == nodeB.data)
return node;
List<Node> children = node.chidren;
int count = 0;
Node lca = null;
for (Node n : children) {
Node tmpNode = lca(n, nodeA, nodeB);
if (tmpNode != null) {
lca = tmpNode;
count++;
}
}
if (count == 2) {
return node;
}
return lca;
}
There are definitely better approaches to traversing the Boss->employee tree, but this is a decent working solution that passes a wide enough arrangement of tests.
//level.h
#include <string>
#include <vector>
using namespace std;
class level
{
public:
struct node
{
string Name;
level* Down;
node(string Name_):Name(Name_),Down(NULL){};
};
string Boss;
int Depth;
vector<node*> Sub;
level(string Boss_, vector<node*> sub_,int d_):Boss(Boss_),Sub(sub_),Depth(d_){};
vector<node*> insertNode(string IDone, string IDtwo, string IDthree)
{
vector<node*> Sub(3);
Sub[0] = new node(IDone);
Sub[1] = new node(IDtwo);
Sub[2] = new node(IDthree);
return Sub;
}
};
//main.cpp
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include "level.h"
using namespace std;
class Hierarchy
{
private:
/*
level* findEmployee(level* t,string Boss_)
{
for(int i=0;i<3;i++)
{
if(t!=NULL && t->Sub[i]->Name.compare(Boss_)==0)
if(t->Sub[i]->Down==NULL)
{
return t;
break;
}
else
cout<<"ERROR: This employee is already a manager";
if(t->Sub[i]->Down)
findEmployee(t->Sub[i]->Down,Boss_);
}
}
*/
void printEmployeeChart(level* t)
{
cout<<"DEPTH: "<<t->Depth<<" "<<t->Boss<<" -> [ ";
for(int i=0; i<3; i++)
cout<<t->Sub[i]->Name<<" ";
cout<<"]"<< endl ;
for(int i=0; i<3; i++)
{
if(t->Sub[i]->Down)
printEmployeeChart(t->Sub[i]->Down);
}
}
level* root;
public:
Hierarchy()
{
root = NULL;
}
void insertCEO(string Boss_, string IDone, string IDtwo, string IDthree)
{
if(root==NULL)
root = new level(Boss_, root->insertNode(IDone,IDtwo,IDthree), 1);
else
cout<<"ERROR: CEO already declared.";
}
void printEmployeeChart()
{
printEmployeeChart(root);
}
void insertLevel(string Boss_, string IDone, string IDtwo, string IDthree,level* t)
{
for(int i=0;i<3;i++)
if(t->Sub[i]->Down)
insertLevel(Boss_,IDone,IDtwo,IDthree,t->Sub[i]->Down);
for(int i=0;i<3;i++)
{
if(t->Sub[i]->Name.compare(Boss_)==0)
if(t->Sub[i]->Down==NULL)
{
t->Sub[i]->Down = new level(Boss_,t->insertNode(IDone,IDtwo,IDthree),(t->Depth+1));
break;
}
else
cout<<"ERROR: This employee is already a manager";
}
}
void insertLevel(string Boss_, string IDone, string IDtwo, string IDthree)
{
insertLevel(Boss_,IDone,IDtwo,IDthree,root);
}
void findEmployee(string ID, level* t, stack<level*> &s,string &Boss)
{
s.push(t);
for(int i=0;i<3;i++)
{
if(t->Sub[i]->Name.compare(ID)==0)
{
Boss = t->Boss;
return;
}
if(t->Sub[i]->Down)
findEmployee(ID,t->Sub[i]->Down,s,Boss);
}
if(s.top()->Boss.compare(Boss)!=0)
s.pop();
}
string closestCommonManager(string IDone,string IDtwo)
{
stack<level*> s1;
stack<level*> s2;
string Boss = "";
findEmployee(IDone,root,s1,Boss);
Boss = "";
findEmployee(IDtwo,root,s2,Boss);
while(s1.size()!=s2.size())
{
if( (s1.size()==(s2.size()+1)) && s1.top()->Boss==IDtwo )
return IDtwo;
else if( (s1.size()+1)==s2.size() && s2.top()->Boss==IDone )
return IDone;
if(s1.size()>s2.size())
s1.pop();
else if(s2.size()>s1.size())
s2.pop();
}
while(s1.top()->Boss!=s2.top()->Boss)
{
s1.pop();
s2.pop();
}
return s1.top()->Boss;
}
};
int main()
{
Hierarchy h;
h.insertCEO("Mark","Alan","Jeff","Jacob");
h.insertLevel("Alan","Ryan","Josh","Jon");
h.insertLevel("Jeff","Cody","Cameron","Kyle");
h.insertLevel("Kyle","Kevin","Christian","Dan");
h.insertLevel("Dan","Derk","Dylan","Jordon");
h.insertLevel("Dylan","Becca","Bobbi","Brit");
h.insertLevel("Ryan","Sam","Charlie","Lisa");
h.printEmployeeChart();
cout<<endl;
//Case 1: Both ID share the same the boss;
cout<<h.closestCommonManager("Ryan","Josh")<<endl; //expect Alan
//Case 2: Same level one ID is The boss;
cout<<h.closestCommonManager("Becca","Dylan")<<endl; //expect Dylan
//Case 3: One ID is deeper than other, both IDs follow along the same branch, neither are bosses.
cout<<h.closestCommonManager("Cody","Kevin")<<endl; //expect jeff
//Case 4: One ID is deeper than other, both IDs follow along the same branch, one is a boss.
cout<<h.closestCommonManager("Kevin","Dylan")<<endl; //expect kyle
//Case 5: IDs follow different branches.
cout<<h.closestCommonManager("Ryan","Cody")<<endl; //expect mark
system("pause");
}
There are definitely better approaches to traversing the Boss->employee tree, but this is a decent working solution that passes a wide enough arrangement of tests.
//level.h
#include <string>
#include <vector>
using namespace std;
class level
{
public:
struct node
{
string Name;
level* Down;
node(string Name_):Name(Name_),Down(NULL){};
};
string Boss;
int Depth;
vector<node*> Sub;
level(string Boss_, vector<node*> sub_,int d_):Boss(Boss_),Sub(sub_),Depth(d_){};
vector<node*> insertNode(string IDone, string IDtwo, string IDthree)
{
vector<node*> Sub(3);
Sub[0] = new node(IDone);
Sub[1] = new node(IDtwo);
Sub[2] = new node(IDthree);
return Sub;
}
};
//main.cpp
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include "level.h"
using namespace std;
class Hierarchy
{
private:
/*
level* findEmployee(level* t,string Boss_)
{
for(int i=0;i<3;i++)
{
if(t!=NULL && t->Sub[i]->Name.compare(Boss_)==0)
if(t->Sub[i]->Down==NULL)
{
return t;
break;
}
else
cout<<"ERROR: This employee is already a manager";
if(t->Sub[i]->Down)
findEmployee(t->Sub[i]->Down,Boss_);
}
}
*/
void printEmployeeChart(level* t)
{
cout<<"DEPTH: "<<t->Depth<<" "<<t->Boss<<" -> [ ";
for(int i=0; i<3; i++)
cout<<t->Sub[i]->Name<<" ";
cout<<"]"<< endl ;
for(int i=0; i<3; i++)
{
if(t->Sub[i]->Down)
printEmployeeChart(t->Sub[i]->Down);
}
}
level* root;
public:
Hierarchy()
{
root = NULL;
}
void insertCEO(string Boss_, string IDone, string IDtwo, string IDthree)
{
if(root==NULL)
root = new level(Boss_, root->insertNode(IDone,IDtwo,IDthree), 1);
else
cout<<"ERROR: CEO already declared.";
}
void printEmployeeChart()
{
printEmployeeChart(root);
}
void insertLevel(string Boss_, string IDone, string IDtwo, string IDthree,level* t)
{
for(int i=0;i<3;i++)
if(t->Sub[i]->Down)
insertLevel(Boss_,IDone,IDtwo,IDthree,t->Sub[i]->Down);
for(int i=0;i<3;i++)
{
if(t->Sub[i]->Name.compare(Boss_)==0)
if(t->Sub[i]->Down==NULL)
{
t->Sub[i]->Down = new level(Boss_,t->insertNode(IDone,IDtwo,IDthree),(t->Depth+1));
break;
}
else
cout<<"ERROR: This employee is already a manager";
}
}
void insertLevel(string Boss_, string IDone, string IDtwo, string IDthree)
{
insertLevel(Boss_,IDone,IDtwo,IDthree,root);
}
void findEmployee(string ID, level* t, stack<level*> &s,string &Boss)
{
s.push(t);
for(int i=0;i<3;i++)
{
if(t->Sub[i]->Name.compare(ID)==0)
{
Boss = t->Boss;
return;
}
if(t->Sub[i]->Down)
findEmployee(ID,t->Sub[i]->Down,s,Boss);
}
if(s.top()->Boss.compare(Boss)!=0)
s.pop();
}
string closestCommonManager(string IDone,string IDtwo)
{
stack<level*> s1;
stack<level*> s2;
string Boss = "";
findEmployee(IDone,root,s1,Boss);
Boss = "";
findEmployee(IDtwo,root,s2,Boss);
while(s1.size()!=s2.size())
{
if( (s1.size()==(s2.size()+1)) && s1.top()->Boss==IDtwo )
return IDtwo;
else if( (s1.size()+1)==s2.size() && s2.top()->Boss==IDone )
return IDone;
if(s1.size()>s2.size())
s1.pop();
else if(s2.size()>s1.size())
s2.pop();
}
while(s1.top()->Boss!=s2.top()->Boss)
{
s1.pop();
s2.pop();
}
return s1.top()->Boss;
}
};
int main()
{
Hierarchy h;
h.insertCEO("Mark","Alan","Jeff","Jacob");
h.insertLevel("Alan","Ryan","Josh","Jon");
h.insertLevel("Jeff","Cody","Cameron","Kyle");
h.insertLevel("Kyle","Kevin","Christian","Dan");
h.insertLevel("Dan","Derk","Dylan","Jordon");
h.insertLevel("Dylan","Becca","Bobbi","Brit");
h.insertLevel("Ryan","Sam","Charlie","Lisa");
h.printEmployeeChart();
cout<<endl;
//Case 1: Both ID share the same the boss;
cout<<h.closestCommonManager("Ryan","Josh")<<endl; //expect Alan
//Case 2: Same level one ID is The boss;
cout<<h.closestCommonManager("Becca","Dylan")<<endl; //expect Dylan
//Case 3: One ID is deeper than other, both IDs follow along the same branch, neither are bosses.
cout<<h.closestCommonManager("Cody","Kevin")<<endl; //expect jeff
//Case 4: One ID is deeper than other, both IDs follow along the same branch, one is a boss.
cout<<h.closestCommonManager("Kevin","Dylan")<<endl; //expect kyle
//Case 5: IDs follow different branches.
cout<<h.closestCommonManager("Ryan","Cody")<<endl; //expect mark
system("pause");
}
public class Node {
String name;
ArrayList<Node> employees;
public Node(String string, ArrayList<Node> object) {
// TODO Auto-generated constructor stub
name = string;
employees = object;
}
public Node() {
// TODO Auto-generated constructor stub
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public ArrayList<Node> getEmployees() {
return employees;
}
public void setEmployees(ArrayList<Node> employees) {
this.employees = employees;
}
}
public class NodeStatus {
int count;
Node node;
public NodeStatus(int i, Node object) {
// TODO Auto-generated constructor stub
count = i;
node = object;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public Node getNode() {
return node;
}
public void setNode(Node node) {
this.node = node;
}
}
public NodeStatus findLowestCommonAncestor(Node root, Node node1, Node node2) {
if (root == null || node1 == null || node2 == null) {
return new NodeStatus(0, null);
}
if (node1 == node2) {
return new NodeStatus(2, node1);
}
if (root.getEmployees() == null || root.getEmployees().isEmpty()) {
if (root.name == node1.name || root.name == node2.name) {
return new NodeStatus(1, null);
}
return new NodeStatus(0, null);
}
ArrayList<Node> employees = root.getEmployees();
NodeStatus currentNodeStatus, levelNodeStatus = new NodeStatus(0, null);
for (int i = 0; i < employees.size(); i++) {
currentNodeStatus = findLowestCommonAncestor(employees.get(i), node1, node2);
if (currentNodeStatus.getCount() == 2) {
return currentNodeStatus;
}
if (currentNodeStatus.getCount() == 1) {
if (root.name.equals(node1.name) || root.name.equals(node2.name) || levelNodeStatus.getCount() == 1) {
return new NodeStatus(2, root);
}
levelNodeStatus.setCount(currentNodeStatus.getCount());
}
}
return levelNodeStatus;
}
public class Node {
String name;
ArrayList<Node> employees;
public Node(String string, ArrayList<Node> object) {
// TODO Auto-generated constructor stub
name = string;
employees = object;
}
public Node() {
// TODO Auto-generated constructor stub
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public ArrayList<Node> getEmployees() {
return employees;
}
public void setEmployees(ArrayList<Node> employees) {
this.employees = employees;
}
}
public class NodeStatus {
int count;
Node node;
public NodeStatus(int i, Node object) {
// TODO Auto-generated constructor stub
count = i;
node = object;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public Node getNode() {
return node;
}
public void setNode(Node node) {
this.node = node;
}
}
public NodeStatus findLowestCommonAncestor(Node root, Node node1, Node node2) {
if (root == null || node1 == null || node2 == null) {
return new NodeStatus(0, null);
}
if (node1 == node2) {
return new NodeStatus(2, node1);
}
if (root.getEmployees() == null || root.getEmployees().isEmpty()) {
if (root.name == node1.name || root.name == node2.name) {
return new NodeStatus(1, null);
}
return new NodeStatus(0, null);
}
ArrayList<Node> employees = root.getEmployees();
NodeStatus currentNodeStatus, levelNodeStatus = new NodeStatus(0, null);
for (int i = 0; i < employees.size(); i++) {
currentNodeStatus = findLowestCommonAncestor(employees.get(i), node1, node2);
if (currentNodeStatus.getCount() == 2) {
return currentNodeStatus;
}
if (currentNodeStatus.getCount() == 1) {
if (root.name.equals(node1.name) || root.name.equals(node2.name) || levelNodeStatus.getCount() == 1) {
return new NodeStatus(2, root);
}
levelNodeStatus.setCount(currentNodeStatus.getCount());
}
}
return levelNodeStatus;
}
employee = {
"BILL" : ["DOM", "SAMIR","MICHAEL"],
"DOM" : ["BOB", "PETER", "PORTER"],
"PETER" : ["MILTON", "NINA"],
}
def dfs_path(graph, end, start = 'BILL', path=None):
if path is None:
path = [start]
if start == end:
yield path
for next in set(graph[start]) - set(path):
try:
for i in dfs_path(graph, end, next, path + [next]):
yield i
except KeyError:
continue
def closestCommonManager(name1,name2):
path_name1 = []
path_name2 = []
for name in dfs_path(employee,name1):
path_name1 += name
for name in dfs_path(employee,name2):
path_name2 += name
max_len = max(path_name1.__len__(),path_name2.__len__())
## print path_name1,path_name2,max_len
for i in range(max_len):
try:
if path_name1[i] != path_name2[i]:
break
except IndexError:
print path_name1[i - 1]
return
print path_name1[i -1]
closestCommonManager('MILTON','NINA') :: PETER
closestCommonManager('PORTER','NINA') :: DOM
closestCommonManager('SAMIR','NINA') :: BILL
closestCommonManager('PETER','NINA') :: PETER
class Employee:
def __init__(self,data):
self.data=data
self.children=[]
def add_child(self,obj):
self.children.append(obj)
def get_name(self):
return self.data
def print_child(self):
print self.data
def print_all_child(self):
for child in self.children:
print child.data
def get_dict_manager_name(root):
dict_name_node={}
dict_name_parent={}
dict_name_node[root.data]=root
list_=[root]
while len(list_) !=0:
node=list_.pop()
for child in node.children:
dict_name_node[child.data]=child
dict_name_parent[child.data]=node
list_.append(child)
return dict_name_parent,dict_name_node
def closest_common_manager(name1,name2):
dict_name_parent,dict_name_node=get_dict_manager_name(root)
node1=dict_name_node[name1]
node2=dict_name_node[name2]
list1=[]
list2=[]
common_ancestor=root
while node1 != root or node2!=root:
if node1==node2:
common_ancestor=node1
break
if node1 in list2:
common_ancestor=node1
break
if node2 in list1:
common_ancestor=node2
break
list1.append(node1)
list2.append(node2)
if node1 !=root:
node1=dict_name_parent[node1.data]
if node2 != root:
node2=dict_name_parent[node2.data]
print "Ancestor of ",name1," and ",name2," is ", common_ancestor.data
#driver program
root=Employee("bill")
dom=Employee("Dom")
root.add_child(dom)
root.add_child(Employee("samir"))
root.add_child(Employee("michael"))
dom.add_child(Employee("bob"))
dom.add_child(Employee("porter"))
peter=Employee("peter")
dom.add_child(peter)
peter.add_child(Employee("milton"))
peter.add_child(Employee("nina"))
closest_common_manager("milton","nina")
closest_common_manager("nina","porter")
closest_common_manager("nina","samir")
closest_common_manager("peter","nina")
Python code :
class Employee:
def __init__(self,data):
self.data=data
self.children=[]
def add_child(self,obj):
self.children.append(obj)
def get_name(self):
return self.data
def print_child(self):
print self.data
def print_all_child(self):
for child in self.children:
print child.data
def get_dict_manager_name(root):
dict_name_node={}
dict_name_parent={}
dict_name_node[root.data]=root
list_=[root]
while len(list_) !=0:
node=list_.pop()
for child in node.children:
dict_name_node[child.data]=child
dict_name_parent[child.data]=node
list_.append(child)
return dict_name_parent,dict_name_node
def closest_common_manager(name1,name2):
dict_name_parent,dict_name_node=get_dict_manager_name(root)
node1=dict_name_node[name1]
node2=dict_name_node[name2]
list1=[]
list2=[]
common_ancestor=root
while node1 != root or node2!=root:
if node1==node2:
common_ancestor=node1
break
if node1 in list2:
common_ancestor=node1
break
if node2 in list1:
common_ancestor=node2
break
list1.append(node1)
list2.append(node2)
if node1 !=root:
node1=dict_name_parent[node1.data]
if node2 != root:
node2=dict_name_parent[node2.data]
print "Ancestor of ",name1," and ",name2," is ", common_ancestor.data
#driver program
root=Employee("bill")
dom=Employee("Dom")
root.add_child(dom)
root.add_child(Employee("samir"))
root.add_child(Employee("michael"))
dom.add_child(Employee("bob"))
dom.add_child(Employee("porter"))
peter=Employee("peter")
dom.add_child(peter)
peter.add_child(Employee("milton"))
peter.add_child(Employee("nina"))
closest_common_manager("milton","nina")
closest_common_manager("nina","porter")
closest_common_manager("nina","samir")
closest_common_manager("peter","nina")
Node ccm(Node n1, Node n2){
n1.visited=true;
n2.visited=true;
while(n1.parent!=null && n2.parent!=null){
if(n1.parent.visited){
return n1.parent;
}
if(n2.parent.visited){
return n2.parent;
}
n1=n1.parent;
n2=n2.parent;
}
if(n1.parent==null){
retrun n1;
}
if(n2.parent==null){
return n2;
}
}
C# - Recursion
private Stack<int> commonManagers = new Stack<int>();
public int GetClosestCommonManagers()
{
return commonManagers.Pop();
}
public void ClosestManager(BinaryTree<int> tree, int firstEmp, int secEmp)
{
if (tree == null) return;
if (HasChild(tree, firstEmp) && HasChild(tree, secEmp))
commonManagers.Push(tree.Node);
ClosestManager(tree.Right, firstEmp, secEmp);
ClosestManager(tree.Left, firstEmp, secEmp);
}
private bool HasChild(BinaryTree<int> tree, int employee)
{
if (tree == null) return false;
if (tree.Node == employee) return true;
return HasChild(tree.Left, employee) || HasChild(tree.Right, employee);
}
- Coder February 14, 2016