Tree: calculate sum of all branches after encoding each branch into a number Python

PHOTO EMBED

Tue Aug 09 2022 00:00:39 GMT+0000 (UTC)

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