find sum of maximum possible triangular chord

Question

I am having a binary tree

         2
       /   \
      3     4
     / \     \
    5   1     8
   / \       / \
  1   6     9   2
                 \
                  4

i want to find the maximum possible triangular chord info sum of nodes ( between any two leaves and a node having both left and right child ) in the given tree.

a triangular chord will be

for triangular chord :

just imagine a line between any two leaves, go upward towards root, find a common parent (that can be parent, grandparent, grandgrandparent or even the root itself). While moving upwards, for each leaf ( for any leaf either we have to go upward only left left left .... and so OR either only right right right right .. and so) means ( left leaf will only move right upward only and right leaf will move left upward only..... So for any single leaf, we can not move in both direction while moving upwards).. Now we get a triangular shape.. in which a side may contain any no. of nodes/links possible.. NOW, if that triangular shape does not contain any extra internal branches. that triangular shape will be a triangular chord.

Do remember that every leaf node is also always a triangular chord (It is just to create the default cases if the binary tree do not have any triangular shaped chord)

now

    maximum triangular chord will be that triangular chord 
which have maximum total in sum of all its node info.

we are required to return that maximum total.

    If we do not have triangular shaped chord.. 
then we have to return the leaf with maximum info.

for example

   8                    
  / \
 2   3
      \
       3

is a triangular chord

  8                     
  / \                   
 2   3
  \   \
   4   1

only subtree with single node 4 will be maximum triangular chord (as its sum is greater than another triangular chord with single node 1) Not the whole tree will be triangular chord

    8                    
   / \
  2   3
 /     \
4       3

is a triangular chord

so the solution of the very first tree on the first line of question is

8+9+2+4 = 23

i am badly trapped in this problem.

I have a rough approach

I will recursively call leftchild as root of subtree and find the left maximum triangular chord sum then same for rightchild as root of subtree.

add the max of leftmax and rightmax, and the add to rood node and return

in c++ mycode is :

int maxtri(node* n) 
{
  if(n) 
  {
    lsum = maxtri(n->left);
    rsum = maxtri(n->right);
    k = maxof(lsum,rsum);
    return (n->info + k);
  }
}

edit : my another recursive approach

int l =0, r =0;
int maxtri(node* n)
{
 if (n == NULL) return 0;
 if (!(n->left) && !(n->right)) return n->info;
 if ((n->left) && (n->right))
 {
  l = maxtri(n->left);
  r = maxtri(n->right);
 }
 if ((n->left) && !(n->right)) 
 {  
  l = l + maxtri(n->left);
 }
 if (!(n->left) && (n->right)) 
 {
  r = r + maxtri(n->right);
 }
 return (l+r+n->info);
}

i have doubt on my approach.

can anyone give another solution.??

Answer 1

What about this logic:
For each node traverse the left portion and right portion, if you find any branches then don't consider this node in your calculation else consider this. Moreover, for the part of calculation node should have left & right nodes or it should be leaf node.

Note: I have not tested it properly but i believe it should work.

// Node by Node traverse the tree  

void addSum(Node *head, vector<int>& sum)
{
if (head == NULL)
    return;
else {
    int s = traverseThisNode(head);
    sum.push_back(s); // Add to vector
    addSum(head->left, sum);
    addSum(head->right, sum);
}
}

// For each node traverse left & right  

int traverseThisNode(Node *head)
{
if (head && head->left && head->right) {
    Node *temp = head;  // To traverse right portion of this node
    int sum = head->value;
    while(head->left) {   // Traverse right
        head = head->left;
        sum = sum + head->value;
        if (head->right) {  // Condition to check if there is any branching
            sum = 0;
            break;
        }
    }
    while(temp->right && sum != 0) {  // Traverse Right now
        temp = temp->right;
        sum = sum + temp->value;
        if (temp->left) { // Condition to check if there is any branching
            sum = 0;
            break;
        }
    }

    return sum;
} else if (head && !head->left && !head->right) {
    return head->value;   // To add leaf node
}
return 0;
}

Now you have vector containing all the value of triangular in the tree, traverse it and   
find the maximum.
int maximum() 
{
  // Traverse the vector "sum" & find the maximum
}