Problem
You are given a binary tree and a number k.
Print the sum of levels k^0, k^1, k^2, k^3..... untill all levels are exhausted.
Each K^ith level sum should be printed separately.
Solution
Calculate the depth of the binary tree
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Print the sum of levels k^0, k^1, k^2, k^3 of binary tree
Created Date : 11-July-2013
Last Modified :
===========================================================================
*/
#include <iostream>
#include <iomanip>
#include <queue>
using namespace std;
typedef struct binTree
{
int key;
struct binTree* left;
struct binTree* right;
}BinTree;
BinTree* NewBinTreeNode(int value)
{
BinTree *node = new BinTree;
node->key = value;
node->left = NULL;
node->right = NULL;
return node;
}
void AddBinTreeNode(BinTree **root, int value)
{
if(*root == NULL){
*root = NewBinTreeNode(value);
}
else{
if(value < (*root)->key){
if((*root)->left == NULL){
(*root)->left = NewBinTreeNode(value);
}
else{
AddBinTreeNode(&((*root)->left), value);
}
}
else{
if((*root)->right == NULL){
(*root)->right = NewBinTreeNode(value);
}
else{
AddBinTreeNode(&((*root)->right), value);
}
}
}
}
void PrintInOrder(BinTree *root)
{
if(root == NULL) return;
PrintInOrder(root->left);
cout << setw(4) << root->key;
PrintInOrder(root->right);
}
void PrintNthLevelTree(BinTree* root, int n)
{
if(n < 0){
cout << "N is less than zero" << endl;
return;
}
if(root == NULL){
cout << "Binary tree is empty" << endl;
return;
}
int index = 0;
queue<BinTree *> nodes;
nodes.push(root);
while(index < n){
queue<BinTree *> nextLevelNodes(nodes);
queue<BinTree *> empty;
nodes.swap(empty);
while(!nextLevelNodes.empty()){
BinTree *node = nextLevelNodes.front();
nextLevelNodes.pop();
if(node->left != NULL){
nodes.push(node->left);
}
if(node->right != NULL){
nodes.push(node->right);
}
}
index ++;
if(nodes.empty()){
cout << "The maximum depth is less than " << n << endl;
return;
}
}
cout << "In " << n << " level:" << endl;
while(!nodes.empty()){
BinTree *node = nodes.front();
nodes.pop();
cout << setw(3) << node->key ;
}
cout << endl;
}
void PrintPowerOfNthLevelTree(BinTree* root, int k)
{
if(root == NULL){
cout << "Binary tree is empty" << endl;
return;
}
int index(0);
queue<BinTree *> nodes;
nodes.push(root);
while(!nodes.empty()){
queue<BinTree *> nextLevelNodes(nodes);
queue<BinTree *> empty;
nodes.swap(empty);
while(!nextLevelNodes.empty()){
BinTree *node = nextLevelNodes.front();
nextLevelNodes.pop();
if(node->left != NULL){
nodes.push(node->left);
}
if(node->right != NULL){
nodes.push(node->right);
}
}
index ++;
}
int sum(0);
int i = 0;
while(i < index){
sum += pow(k, i);
cout << "k = " << k << endl;
cout << "Sum of Level " << i << " is " << sum << endl;
i ++;
}
cout << endl;
}
int main(int argc, char* argv[])
{
int testCase1[] = {3, 7, 6, 2, 1, 8, 9, 3, 7, 4, 5};
BinTree* root = NULL;
for(int i = 0; i < sizeof(testCase1)/sizeof(testCase1[0]); ++i)
{
AddBinTreeNode(&root, testCase1[i]);
}
cout << "Display in order" << endl;
PrintInOrder(root);
cout << "\n--------------------" << endl;
for(int i = 6; i >= 0; --i){
PrintPowerOfNthLevelTree(root, i);
}
return 0;
}
Output
Display in order
1 2 3 3 4 5 6 7 7 8 9
--------------------
k = 6
Sum of Level 0 is 1
k = 6
Sum of Level 1 is 7
k = 6
Sum of Level 2 is 43
k = 6
Sum of Level 3 is 259
k = 6
Sum of Level 4 is 1555
k = 6
Sum of Level 5 is 9331
k = 5
Sum of Level 0 is 1
k = 5
Sum of Level 1 is 6
k = 5
Sum of Level 2 is 31
k = 5
Sum of Level 3 is 156
k = 5
Sum of Level 4 is 781
k = 5
Sum of Level 5 is 3906
k = 4
Sum of Level 0 is 1
k = 4
Sum of Level 1 is 5
k = 4
Sum of Level 2 is 21
k = 4
Sum of Level 3 is 85
k = 4
Sum of Level 4 is 341
k = 4
Sum of Level 5 is 1365
k = 3
Sum of Level 0 is 1
k = 3
Sum of Level 1 is 4
k = 3
Sum of Level 2 is 13
k = 3
Sum of Level 3 is 40
k = 3
Sum of Level 4 is 121
k = 3
Sum of Level 5 is 364
k = 2
Sum of Level 0 is 1
k = 2
Sum of Level 1 is 3
k = 2
Sum of Level 2 is 7
k = 2
Sum of Level 3 is 15
k = 2
Sum of Level 4 is 31
k = 2
Sum of Level 5 is 63
k = 1
Sum of Level 0 is 1
k = 1
Sum of Level 1 is 2
k = 1
Sum of Level 2 is 3
k = 1
Sum of Level 3 is 4
k = 1
Sum of Level 4 is 5
k = 1
Sum of Level 5 is 6
k = 0
Sum of Level 0 is 1
k = 0
Sum of Level 1 is 1
k = 0
Sum of Level 2 is 1
k = 0
Sum of Level 3 is 1
k = 0
Sum of Level 4 is 1
k = 0
Sum of Level 5 is 1
Press any key to continue . . .