Tree: calculate sum of all branches after encoding each branch into a number Python
Tue Aug 09 2022 00:00:39 GMT+0000 (Coordinated Universal Time)
Saved by
@bryantirawan
#python
#methods
#queue
#codesignal
#first
#search
#max
#depth
class Tree(object):
def __init__(self, x, left=None, right=None):
self.value = x
self.left = left
self.right = right
x = Tree(1, Tree(0, Tree(1), Tree(3)), Tree(4))
def solution(t):
if not t:
return 0
stack = [(t, 0)]
branchesSum = 0
while stack:
node, v = stack.pop()
if node.left or node.right:
#depth first search
# the v is a little confusing to understand but easier to see in python tutor
# it goes from 1 to 10 to 100 etc. based on the height of the branch
# can probably do something like str() and converting back to int() as well
if node.left:
stack.append((node.left, node.value + v * 10))
if node.right:
stack.append((node.right, node.value + v * 10))
else:
branchesSum += node.value + v * 10
return branchesSum
content_copyCOPY
t = {
"value": 1,
"left": {
"value": 0,
"left": {
"value": 3,
"left": null,
"right": null
},
"right": {
"value": 1,
"left": null,
"right": null
}
},
"right": {
"value": 4,
"left": null,
"right": null
}
}
should result in 103 + 101 + 14 = 218
https://app.codesignal.com/interview-practice/task/2oxNWXTS8eWBzvnRB/description
Comments