Q:

Print Boundary Sum of a Binary Tree

0

Print Boundary Sum of a Binary Tree

Given a binary tree, print the boundary sum of the tree.

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

First of all we need to understand what the boundary sum of a binary tree is? It's simply the cumulative sum of all boundary nodes surrounding the tree. For the following example:

print boundry sum of a binary tree

The boundary nodes are: 2, 7, 2, 5, 11, 4, 9, and 5 (from left to right direction)

So there are four types of node considered to be boundary node:

  1. Root node
  2. All the leaf nodes
  3. All the nodes at the leftmost side (there will be a duplicate since the last leftmost node is itself a leaf node, discard the duplicate)
  4. All the nodes at the rightmost side ( there will be a duplicate since the last rightmost node is itself a leaf node, discard the duplicate)

Thus, the boundary sum is: 45

Algorithm:

    1. Set sum=0
    2. Add root->data to sum; (type-1 boundary node)
    3. Find all the leaf nodes & add their values respectively. (type-2 boundary node)
      For this portion we do a level-order traversal & keep checking whether the traversed node has both its left & right point NULL or not.
      If the traversed node has both its pointer NULL then it’s a leaf node & of course add to sum cumulatively.
    4. Find the leftmost nodes (without leaf node) & add their respective values. (type-3 boundary node)
      Set temp to root->left
while(!(temp->right==NULL&&temp->left==NULL)){//avoiding leaf node
    sum+=temp->data; //add temp->data
    //always tend to move left side 
    //first for left most nodes
    if(temp->left) 
        temp=temp->left;
    else
        temp=temp->right;
}
    1. Find the rightmost nodes (without leaf node) & add their respective values. (type-4 boundary node)
      Set temp to root->right
while(!(temp->right==NULL&& temp->left==NULL)){//avoiding leaf node
    sum+=temp->data;//add temp->data
    //always tend to move right side 
    //first for right most nodes
    if(temp->right) 
        temp=temp->right;
    else
        temp=temp->left;
}

C++ program to print Boundary Sum of a Binary Tree

#include <bits/stdc++.h>
using namespace std;

// tree node is defined
class tree{
	public:
		int data;
		tree *left;
		tree *right;
};


int findBoundarySum(tree* root){ //finding boundary sum
if(root==NULL) //base case
	return 0;
int sum=0; //(step1)
sum+=root->data; //add root value (step2)

//find the leaf nodes & add(step3)
tree* temp=root, *store; //copy root to temp
queue<tree*> q; //creat a queue to store tree* variables (pointer to nodes)

//doing level order traversal
q.push(temp);
while(!q.empty()){
	store=q.front();
	q.pop();
	// if left & right both pointers are NULL, it's a leaf node
	if(store->left==NULL && store->right==NULL) 
		sum+=store->data; // add leaf node value
	if(store->left)
		q.push(store->left);
	if(store->right)
		q.push(store->right);
}

/////end of step3////////


//adding the leftmost nodes excluding leaf node(step4)///////////
temp=root->left;
while(!(temp->right==NULL && temp->left==NULL)){//avoiding leaf node
	sum+=temp->data;
	if(temp->left)
		temp=temp->left;
	else
		temp=temp->right;
}

////end of step4//////////

//adding the rightmost nodes excluding leaf node(steps)///////////
temp=root->right;
while(!(temp->right==NULL && temp->left==NULL)){//avoiding leaf node
	sum+=temp->data;
	if(temp->right)
		temp=temp->right;
	else
		temp=temp->left;
}
////end of step5//////////
//boundary sum is now calculated, return it
return sum;
}

// creating new node
tree* newnode(int data)  
{ 
	tree* node = (tree*)malloc(sizeof(tree)); 
	node->data = data; 
	node->left = NULL; 
	node->right = NULL; 
	return(node); 
} 

int main() 
{ 
	//**same tree is builted as shown in example**
	cout<<"Tree is built like the example aforesaid"<<endl;
	//building the tree like as in the example
	tree *root=newnode(2); 
	root->left= newnode(7); 
	root->right= newnode(5); 
	root->right->right=newnode(9);
	root->right->right->left=newnode(4);
	root->left->left=newnode(2); 
	root->left->right=newnode(6);
	root->left->right->left=newnode(5);
	root->left->right->right=newnode(11);

	cout<<"finding boundary sum......"<<endl; 
	cout<<"boundary sum is "<<findBoundarySum(root)<<endl;

	return 0; 
} 

Output

Tree is built like the example aforesaid
finding boundary sum......
boundary sum is 45

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now