CODEWITHSUNDEEP
algorithmrecursiontreebinary-treebinary-search-tree
Aaron7
Aaron7

Reputation: 277

Finding the largest sum of disjoint leaf-to-leaf paths in a binary tree

I need advice on a task where I am looking for disjoint paths leading from leaf to leaf (they must not return along the same path/edge) so that their sum creates the greatest possible value, i.e. the paths must not intersect and must be as good as possible belongs to the total. And be careful, the point (root) where the path breaks is not included in the total sum, viz. picture.

I don't know how to solve the problem at all. I am attaching code that tries to decide whether to choose a path by one leaf or to choose a smaller subtree, but it does not work correctly.

If anyone has any study material I would be very grateful. Thank you in advance All program https://onecompiler.com/c/3ymb7xvzn

int depth(struct node *root, int *res)
{
    if(root == NULL) return 0;
    
    int l = depth(root->left, res);
    int r = depth(root->right, res);
    
    int max_single_best_Way = max(l+root->data, r+root->data);

    int max_root = l+r;
    
    int maximum = max(max_single_best_Way, max_root);
    *res = max(*res, maximum);

    return maximum;

}

enter image description hereenter image description here

enter image description here

enter image description here

I was unable to create an algorithm to solve the problem. I would like some advice, study materials that I could use in the solution.

Upvotes: 1

Views: 179

Answers (1)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Let's call the function, f, our overall task, with input parameter a root to a tree. Let's call the function, g, the maximum continuously descending path from a given node, including the node, that also adds the result of f for each node not chosen.

Starting at the root of the tree, in a run of f, for each node, we can either assign it (1) as a parent in a path, or (2) not part of any path. In the case of (1), we'd like g(left_child) + g(right_child). In the case of (2), we'd like f(left_child) + f(right_child).

Python code with your second example, where the root is not part of any path:

def g(tree):
  if tree == None:
    return 0
  return tree["val"] + max(
    g(tree["l"]) + f(tree["r"]),
    g(tree["r"]) + f(tree["l"])
  )

def f(tree):
  if tree == None:
    return 0
  return max(
    g(tree["l"]) + g(tree["r"]),
    f(tree["l"]) + f(tree["r"])
  )
  
tree = {
  "val": 0,
  
  "l": {
    "val": 2,
    
    "l": {
      "val": 2,
      "l": None,
      "r": None
    },
    
    "r": {
      "val": 3,
      "l": None,
      "r": None
    }
  },
  
  "r": {
    "val": 1,
    
    "l": {
      "val": 2,
      "l": None,
      "r": None
    },
    
    "r": {
      "val": 3,
      "l": None,
      "r": None
    }
  }
}

print(f(tree)) # 10

Your third example:

tree = {
  "val": 0,
  
  "l": {
    "val": 6,
    
    "l": {
      "val": 5,
      "l": None,
      "r": None
    },
    
    "r": {
      "val": 3,
      "l": None,
      "r": None
    }
  },
  
  "r": {
    "val": 5,
    
    "l": {
      "val": 7,
      
      "l": {
        "val": 3,
        "l": None,
        "r": None
      },
    
      "r": {
        "val": 6,
        "l": None,
        "r": None
      }
    },
    
    "r": {
      "val": 7,
      
      "l": {
        "val": 6,
        "l": None,
        "r": None
      },
    
      "r": {
        "val": 7,
        "l": None,
        "r": None
      }
    }
  }
}

print(f(tree)) # 42

Upvotes: 1

Related Questions