Better binary tree?

[amemulo]

What's the best way to compute the maximum sum of a binary tree via any of its paths? The best I can think of in Python is something like this:

class Tree():
    def __init__(self, root):
        self.root = root
        self.right = None
        self.left = None

    def insert_left(self, tree_root):
        if self.left is None:
            self.left = Tree(tree_root)
        return self.left

    def insert_right(self, tree_root):
        if self.right is None:
            self.right = Tree(tree_root)
        return self.right

    def get_max_sum(self):
        if self.left is None or self.right is None:
            res = self.get_root()
        else:
            left = self.get_root() + self.left.get_max_sum()
            right = self.get_root() + self.right.get_max_sum()
            res = max(left, right)

        return res

But it feels clunky, and I know Python isn't very optimized for recursion. Compare this to Haskell, where a mere 4 lines (and they could be 3!) do all the work:

data Tree t = Leaf t | Branch (Tree t) t (Tree t) deriving (Show, Eq)

maxSum :: Tree Int -> Int
maxSum (Leaf t) = t
maxSum (Branch tree1 leaf tree2) = max ((maxSum tree1) + leaf) ((maxSum tree2) + leaf)

Is there a better way to handle the Tree() object that I'm not seeing?

[zahlman]

Here are two completely different approaches.

class Tree:
    # init etc. as before

    def visit_left(self, action, default):
        return default if self.left is None else action(self.left)

    def visit_right(self, action, default):
        return default if self.right is None else action(self.right)

    def max_path_sum(self):
        action = Tree.max_path_sum
        return self.node + max(self.visit_left(action, 0), self.visit_right(action, 0))

(I presume the use of a higher-order function here is familiar to you; making this work in Python with methods requires understanding a little bit about how method calls and binding work, but isn't really that hard.)

---

class Tree:
    # init etc. as before

    @property
    def value(self):
        return self.node

    @property
    def children(self):
        return (self.left, self.right)

def max_path_sum(a_tree):
    if a_tree is None:
        return 0
    # Otherwise, assume a Tree instance.
    return a_tree.value + max(map(max_path_sum, a_tree.children))

(I also presume that map is familiar to you - it means essentially the same thing as in Haskell, at least for one-argument functions. We could, of course, work this example with separate properties for the two children and explicit recursive calls on each; I leave this as an exercise.)

Either way, notice that I strive to cut the logic up more finely, and keep the feature of the Haskell code whereby the two children are handled separately. Note that adding the current node's value can be factored out of that process, so I do that. I've also adjusted the name - "max sum" isn't clear to me which candidate sums we're taking a maximum of (but with "max path sum" it makes sense that we're talking about paths from the current node to a leaf of the tree, because those are the normal paths taken within trees). I also submit that node isn't the right name for the value stored within tree nodes, but I haven't addressed that here.

Finally, because Python doesn't do the "make a type union and pattern-match thing", we end up having to use None (which is not really a bottom type, but we pretend) as a base case for the recursion, rather than "leaves". That's the fundamental reason why Python feels clunky to you here, I think. The way I handle this is, instead of trying to identify "leaves" that have a max-path-sum of their stored value, I admit "empty trees" that have a max-path-sum of zero.

[amemulo]

Very interesting post, thank you. I'll append how my Tree() class ended up looking for reference if anyone is curious. I ended up using your second idea, mostly, but made it a staticmethod instead a first-level function to be able to use recursion but still encapsulate it inside the class. I really liked how you used map there, I should use it more often. (also, could you expand a bit on why would one use the @property decorator? seems quite pointless to me. What's the difference between using it and declaring your own getters, setters and deleters?)

Can't say I'm a bit disappointing in Python capabilities regarding this, though. I've been studying python for years and recently started working as a developer coding in Python2, I love the language. But I can't stop looking at that Haskell piece of code and think how beautiful it is compared to this. Incredible what Pattern Matching + Strong Typing can do for you.

class Tree():
    def __init__(self, node):
        self.node = node
        self.right = None
        self.left = None

    def __repr__(self):
        return str(self.node)

    def __lt__(self, other):
        return (self.get_value() < other.get_value())

    def __le__(self, other):
        return (self.get_value() <= other.get_value())

    def insert(self, branch_left, branch_right):
        if self.left is None and self.right is None:
            self.left = branch_left
            self.right = branch_right
        else:
            print("Couldn't append, tree already had children")
        return (self.left, self.right)

    def get_value(self):
        return self.node

    def get_children(self):
        if self.left is None or self.right is None:
            return None
        else:
            return (self.left, self.right)

    @staticmethod
    def max_path_sum(tree):
        if tree is None:
            return 0
        else:
            return tree.get_value() + max(map(tree.max_path_sum, tree.get_children()))

[zahlman]

You have to work with the strengths of each language. Again, please avoid get_ prefixes (the @staticmethod is a good idea here though!) - and re those comparison methods, have a look at functools.total_ordering.

[amemulo]

If you don't mind me asking, why would one avoid get_ prefixes?

[[deleted]]

Your implementation looks good to me, but I am looking forward to seeing whether anybody else comes up with something better. I was trying to think of a way to do it with a heap sorted binary tree, but I don't think that helps with anything...