Python algorithm for finding max path in binary tree not working as desired

Question

I was trying to write a Python algorithm that would find the maximum sum for a path of integers in a binary tree. I thought that the easiest way to do this would be a recursive function, but this doesn't seem to work the way I intended. How could I revise this function so that it would find the absolute maximum path? I can confirm that building the tree is working fine so far because the height function I wrote for it worked as intended.

class Node:
    def __init__(self, data):
        self.right = self.left = None
        self.data = data

class Solution:
    def insert(self, root, data):
        if not root:
            return Node(data)
        else:
            if data<=root.data:
                cur=self.insert(root.left, data)
                root.left=cur
            else:
                cur=self.insert(root.right, data)
                root.right=cur
        return root

def get_height(self, root):
    if not root or root.left == root.right == None:
        return 0
    return 1 + max(self.get_height(root.left), self.get_height(root.right))

def get_max_sum(self, root):
    if not root:
        return 0
    return root.data + max(self.get_max_sum(root.left), self.get_max_sum(root.right))

IO code:

 nums = '''75
    95 64
    17 47 82
    18 35 87 10
    20 04 82 47 65
    19 01 23 75 03 34
    88 02 77 73 07 63 67
    99 65 04 28 06 16 70 92
    41 41 26 56 83 40 80 70 33
    41 48 72 33 47 32 37 16 94 29
    53 71 44 65 25 43 91 52 97 51 14
    70 11 33 28 77 73 17 78 39 68 17 57
    91 71 52 38 17 14 91 43 58 50 27 29 48
    63 66 04 68 89 53 67 30 73 16 69 87 40 31
    04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'''.replace('\n', ' ')
    nums = tuple(map(int, nums.split(' ')))

    tree = Solution()
    root = None
    for i in nums:
        data = i
        root = tree.insert(root, data)

    height = tree.get_height(root)
    msum = tree.get_max_sum(root)
    print(height, msum)

@ggorlen it's supposed to be root to last leaf, so traversing the whole tree. i think it's currently doing that but the value it's finding isn't the maximum path sum — rudiejd
– rudiejd, Commented Jan 19, 2019 at 18:34
root to "last leaf"? Do you mean to any leaf, meaning the one that provides the max path? — trincot
– trincot, Commented Jan 19, 2019 at 18:35
@trincot yes, but considering the structure of the tree i have ( a pyramid where leaves are integers with random values 0-99), it's always going to be the last one since that's the path that goes the most leaves — rudiejd
– rudiejd, Commented Jan 19, 2019 at 18:37
"goes the most leaves". If it's a root-to-leaf path, how can that path go to more than one leaf? I'm confused. Can you show expected I/O and perhaps a tree diagram illustrating what you're trying to accomplish? — ggorlen
– ggorlen, Commented Jan 19, 2019 at 18:44

ggorlen · Accepted Answer · 2019-01-19 19:36:17Z

This code makes a couple faulty assumptions about the problem which explain why it isn't working as you expect.

The input is a graph, not a tree. Looking at this sample input where we're asked to find the maximum root-to-leaf path,
```
   3
  7 4
 2 4 6
8 5 9 3
```
We can observe the following relationships between nodes:
```
      3
     / \
    ↓   ↓
    7   4
   / \ / \
  ↓   ↓   ↓
  2   4   6
 / \ / \ / \
↓   ↓   ↓   ↓
8   5   9   3
```
Because each interior node has two children, you must have (understandably) arrived at the conclusion that it's a tree. But the definition of a tree is that each child have no more than one parent, so we have a contradiction. This is actually a directed acyclic graph.
Even if it were a tree, making it a BST fundamentally changes its structure. Consider the above input once again. Running your insert algorithm on it produces the following binary search tree structure:
```
         3
        / \
       /   \
      /     \
     2       7
      \     / \
       3   4   8
          / \   \ 
         4   6   9
            /
           5
```
Clearly, this structure has little to do with the original input, and running a max path sum algorithm on this structure would yield 3 + 7 + 8 + 9 = 27, when the correct answer is 3 + 7 + 4 + 9 = 23.

I recommend re-formulating the problem as a graph problem and proceeding from there.

Collectives™ on Stack Overflow

Python algorithm for finding max path in binary tree not working as desired

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related