Find the sum of the maximum possible triangular chord

Question

I have 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 nodes (between any two sheets and a node with left and right children) in this tree.

triangular chord will

for a triangular chord:

just imagine the line between any two leaves, go up to the root, find a common parent (who may be the parent, grandfather, grandmother, or even the root itself). When moving up, for each sheet (for any sheet, either we should go up only left left ... and so OR or right right right right .. and so) means (left sheet will move only right up only and the right sheet will move left only up ..... So, for any single sheet 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 a side may contain any no. of nodes/links possible .. NOW, if it is a triangular shape does not contain any extra internal branches , that triangular shape will be a triangular chord.

Remember that every leaf node is also always a triangular chord (just create default cases if the binary tree does not have triangular chords)

now

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

we need return that maximum total.

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

eg

  8 / \ 2 3 \ 3 

- triangular chord

  8 / \ 2 3 \ \ 4 1 

only a subtree with a single node 4 will be the maximum triangular chord (since its sum is larger than another triangular chord with a single node 1). Not the whole tree will be a triangular chord

  8 / \ 2 3 / \ 4 3 

- triangular chord

therefore the solution of the very first tree in the first line of the question

 8+9+2+4 = 23 

I got into this problem badly.

I have a rude approach

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

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

in C ++ mycode:

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

edit: my other 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 doubts about my approach.

can someone give another solution.

Answer 1

How about this logic:
For each node, cross the left side and the right side, if you find any branches, then do not consider this node in your calculation, otherwise consider this. Moreover, for the calculation part, the node must have left and right nodes, or it must be a leaf node.

Note. I have not tested it correctly, but I believe that 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 } 

Answer 2

I am writing pseudo code for my approach, as far as I understand the question.

 Max = min_value; //possibly 0 if no negative value is allowed for nodes. sum = 0; for each node in the tree temp = node; sum+= temp->data //collects data at the current level, the current level may be leaf too. Until temp->left is not null, // Traversing uni-directionally to the left most deep and collecting data. temp = temp->left sum+=temp->data Until temp->right is not null, // Traversing uni-directionally to the right most deep and collecting data. temp = temp->right sum+= temp->data if(sum > Max) Max = sum; sum = 0; print Max;