Hi , I did get an interview question to find the errors in a binary tree. Need help in reviewing the code i wrote.
Sample Input #01
(A,B) (A,C) (B,D) (D,C)
Sample Output #01
E3
Explanation
Node D is both a child of B and a parent of C, but C and B are both child nodes of A.
Since D tries to attach itself as parent to a node already above it in the tree, this forms a cycle.
The list of errors with their codes is as follows:
Error Code Type of error
E1 More than 2 children
E2 Duplicate Edges
E3 Cycle present
E4 Multiple roots
E5 Any other error
I did write a code for this , but need to know how correct i am. And any example errors of Error E5 ? i couldnt find any.
def countRoots(inputStr) :
root="";
for i in range(1,len(input) ,4):
p = input[i];
c = input[i+1]
print(i , c,p)
if p not in parentChild:
parentChild[p] = [ c ] ;
else :
if c in parentChild[p] :
return -3,root; #code for E2
parentChild[p].append(c);
if len(parentChild[p]) > 2 :
return -1,root ; #code for E1
if c not in childParent :
childParent[input[i+1]] = input[i]
else :
return -2,root; #code for E3
visited = {};
rootCount = 0;
for key, value in childParent.items():
child = key;
while child not in visited :
visited[child] = True;
if child in childParent :
child = childParent[child];
else :
rootCount += 1;
print(child , rootCount)
root = child;
print(root)
break;
return rootCount,root;
if count == -1 :
print("E1");
elif count == -2 or count == 0 :
print("E3");
elif count == -3 :
print("E2");
elif count > 1 :
print("E4");
elif count == 1 :
print("Binary Tree , root =,rootCount " , root , rootCount);
print(exp)
else :
print("E5");Is this code correct ? or did i miss any case ?