-
Notifications
You must be signed in to change notification settings - Fork 17
/
ContainsX.py
47 lines (44 loc) · 1.14 KB
/
ContainsX.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)
class treeNode:
def __init__(self, data):
self.data = data
self.children = []
def __str__(self):
return str(self.data)
def containsX(tree, x):
#############################
# PLEASE ADD YOUR CODE HERE #
#############################
if tree is None:
return False
if tree.data == x:
return True
childCount = len(tree.children)
for i in range(childCount):
if (containsX(tree.children[i], x)):
return True
return False
def createLevelWiseTree(arr):
root = treeNode(int(arr[0]))
q = [root]
size = len(arr)
i = 1
while i<size:
parent = q.pop(0)
childCount = int(arr[i])
i += 1
for j in range(0,childCount):
temp = treeNode(int(arr[i+j]))
parent.children.append(temp)
q.append(temp)
i += childCount
return root
# Main
arr = list(int(x) for x in stdin.readline().strip().split())
x=int(stdin.readline().strip())
tree = createLevelWiseTree(arr)
if containsX(tree,x):
print('true')
else:
print('false')