Print all K-sum levels in a Binary Tree
The problem is to print all the levels in a binary tree where the sum of the nodes' values in that level is equal to a given value K.
Problem Statement
Given a binary tree and an integer K, the task is to print all the levels in the binary tree where the sum of the nodes' values in that level is equal to K.
Example Scenario
Consider the binary tree shown below:
10
/ \
2 3
/ / \
4 1 5
/ \ \ \
7 3 6 11
/ \ /
5 8 -3
/ \
-1 11
For this tree, if K is 10, then the levels with the sum of nodes' values equal to 10 are:
- Level 1: 10
- Level 2: 4 1 5
- Level 3: 5 8 -3
- Level 4: -1 11
Idea to Solve the Problem
We can use a BFS (Breadth-First Search) approach to traverse the binary tree level by level and calculate the sum of nodes' values in each level. We'll keep track of the level and sum for each node in a queue. As we traverse each level, we'll check if the sum equals K and print the nodes' values if it does.
Pseudocode
void level_sum(struct Node *root, int k)
{
// Check if the root is NULL
if (root == NULL)
{
printf("Empty Tree\n");
return;
}
// Initialize a queue
// Enqueue the root node with level 1
// Initialize level, sum, and status
while (queue is not empty)
{
// Traverse the current level
// Calculate sum of nodes' values
// If sum equals K, print the nodes' values
// Dequeue nodes from the queue
}
}
Algorithm Explanation
- Implement the
level_sum
function that takes the root of the binary tree and integer K as input. - Check if the root is NULL, if so, print "Empty Tree" and return.
- Initialize a queue data structure for the BFS traversal.
- Enqueue the root node along with its level (starting from 1).
- Start a loop that continues until the queue is empty.
- Inside the loop, traverse the current level and calculate the sum of nodes' values in that level.
- If the sum equals K, set a status flag to 1.
- Traverse the queue again and print the nodes' values if the status flag is set to 1.
- Dequeue nodes from the queue as you process them.
- This process ensures that all levels are traversed, and the nodes with sum equal to K are printed.
Code Solution
// C program
// Print all K-sum levels in a Binary Tree
#include <stdio.h>
#include <stdlib.h>
//Node of binary tree
struct Node
{
int data;
struct Node *left, *right;
};
struct MyQueue
{
int level;
struct Node *element;
struct MyQueue *next;
};
//Create a binary tree nodes and node fields (data,pointer)
//And returning the reference of newly nodes
struct Node *insert(int data)
{
//create dynamic memory to new binary tree node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//Set node value
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
printf("Memory Overflow\n");
}
//return reference
return new_node;
}
//Create a queue node and returns this node
struct MyQueue *enqueue(struct Node *tree_node)
{
//Make a new Queue node
struct MyQueue *new_node = (struct MyQueue *) malloc(sizeof(struct MyQueue));
if (new_node != NULL)
{
//Set node values
new_node->element = tree_node;
new_node->next = NULL;
}
else
{
printf("Memory Overflow\n");
}
return new_node;
}
//Remove a queue elements
void dequeue(struct MyQueue **front)
{
if ( *front != NULL)
{
struct MyQueue *remove = *front;
//Visit to next node
*front = remove->next;
remove->element = NULL;
remove->next = NULL;
//free node
free(remove);
remove = NULL;
}
}
//Print all levels which sum is equal to given value
void level_sum(struct Node *root, int k)
{
if (root != NULL)
{
//make a queue pointers
struct MyQueue *front = NULL, *tail = NULL;
struct MyQueue *temp = NULL;
//Get first node of tree
front = enqueue(root);
//Start level of first node is one
front->level = 1;
//Set tail node to first node
tail = front;
struct Node *node = root;
// Start to first node
temp = front;
// Get level elements into a queue
while (temp != NULL)
{
//Tree node
node = temp->element;
if (node->left != NULL)
{
//Add new left child node
tail->next = enqueue(node->left);
tail->next->level = temp->level + 1;
tail = tail->next;
}
if (node->right != NULL)
{
//Add new right child node
tail->next = enqueue(node->right);
tail->next->level = temp->level + 1;
tail = tail->next;
}
//Visit to next node queue
temp = temp->next;
}
//result node indicator
int status = 0;
int level = 0;
int sum = 0;
while (front != NULL)
{
level = front->level;
status = 0;
sum = 0;
temp = front;
//Calculate the sum of level node
while (temp != NULL && temp->level == level)
{
sum += temp->element->data;
temp = temp->next;
}
if (sum == k)
{
//When k sum exist
status = 1;
printf(" [");
}
// Traversal the tree level
while (front != NULL && front->level == level)
{
if (status == 1)
{
//When sum is equal to k
printf(" %d", front->element->data);
}
//remove a queue node
dequeue( &front);
}
if (status == 1)
{
printf(" ]\n");
}
}
tail = NULL;
}
else
{
printf("Empty Tree\n");
}
}
int main()
{
struct Node *root = NULL;
/*
Construct Binary Tree
-----------------------
10
/ \
2 3
/ / \
4 1 5
/ \ \ \
7 3 6 11
/ \ /
5 8 -3
/ \
-1 11
-----------------------
*/
//Add node
root = insert(10);
root->left = insert(2);
root->right = insert(3);
root->right->right = insert(5);
root->right->left = insert(1);
root->left->left = insert(4);
root->left->left->left = insert(7);
root->left->left->right = insert(3);
root->right->left->right = insert(6);
root->right->right->right = insert(11);
root->right->right->right->left = insert(-3);
root->left->left->right->left = insert(5);
root->left->left->right->right = insert(8);
root->left->left->right->right->left = insert(-1);
root->left->left->right->right->right = insert(11);
level_sum(root, 10);
return 0;
}
Output
[ 10 ]
[ 4 1 5 ]
[ 5 8 -3 ]
[ -1 11 ]
/*
Java program
Print all K-sum levels in a Binary Tree
*/
//Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
public TreeNode element;
public QueueNode next;
public int level;
public QueueNode(TreeNode element, int level)
{
this.element = element;
this.next = null;
this.level = level;
}
}
//Define custom queue class
class MyQueue
{
public QueueNode front;
public QueueNode tail;
public MyQueue()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
public void enqueue(TreeNode element, int level)
{
QueueNode new_node = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
//Add node at last position
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
public boolean is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
public boolean is_k_level_sum(MyQueue queue, int level, int k)
{
if (queue.is_empty() == true)
{
return false;
}
int sum = 0;
QueueNode temp = queue.front;
//Count number of nodes in given level
while (temp != null && temp.level == level)
{
sum += temp.element.data;
temp = temp.next;
}
if (sum == k)
{
return true;
}
else
{
return false;
}
}
//Print all levels which sum is equal to given value
public void level_sum(int k)
{
if (this.root == null)
{
System.out.print("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
TreeNode node = this.root;
//Create a Queue
MyQueue queue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
QueueNode temp = queue.front;
int level = 0;
//Add tree level
while (temp != null)
{
node = temp.element;
level = temp.level;
if (node.left != null)
{
//Add left node
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
//Add right node
queue.enqueue(node.right, level + 1);
}
temp = temp.next;
}
boolean status = false;
level = 0;
while (queue.is_empty() == false)
{
level = queue.front.level;
status = is_k_level_sum(queue, level, k);
if (status == true)
{
System.out.print(" [");
}
// When level nodes sum is equal to k,
// Then this loop are printed node value and remove level nodes
// Otherwise it's removing current level nodes
while (queue.is_empty() == false && queue.front.level == level)
{
if (status == true)
{
//When sum exist
System.out.print(" " + queue.front.element.data);
}
//remove a queue node
queue.dequeue();
}
if (status == true)
{
System.out.print(" ]\n");
}
}
}
}
public static void main(String[] args)
{
//Object of Binary Tree
BinaryTree tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/ \
2 3
/ / \
4 1 5
/ \ \ \
7 3 6 11
/ \ /
5 8 -3
/ \
-1 11
-----------------------
*/
//Add node
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(5);
tree.root.right.left = new TreeNode(1);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(3);
tree.root.right.left.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.left = new TreeNode(-3);
tree.root.left.left.right.left = new TreeNode(5);
tree.root.left.left.right.right = new TreeNode(8);
tree.root.left.left.right.right.left = new TreeNode(-1);
tree.root.left.left.right.right.right = new TreeNode(11);
tree.level_sum(10);
}
}
Output
[ 10 ]
[ 4 1 5 ]
[ 5 8 -3 ]
[ -1 11 ]
//Include header file
#include <iostream>
using namespace std;
/*
C++ program
Print all K-sum levels in a Binary Tree
*/
//Binary Tree node
class TreeNode
{
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
//set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Queue Node
class QueueNode
{
public: TreeNode *element;
QueueNode *next;
int level;
QueueNode(TreeNode *element, int level)
{
this->element = element;
this->next = NULL;
this->level = level;
}
};
//Define custom queue class
class MyQueue
{
public: QueueNode *front;
QueueNode *tail;
MyQueue()
{
this->front = NULL;
this->tail = NULL;
}
//Add a new node at last of queue
void enqueue(TreeNode *element, int level)
{
QueueNode *new_node = new QueueNode(element, level);
if (this->front == NULL)
{
//When first node of queue
this->front = new_node;
}
else
{
//Add node at last position
this->tail->next = new_node;
}
this->tail = new_node;
}
//Delete first node of queue
void dequeue()
{
if (this->front != NULL)
{
QueueNode *temp = this->front;
if (this->tail == this->front)
{
this->tail = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
}
delete temp;
}
}
bool is_empty()
{
if (this->front == NULL)
{
return true;
}
else
{
return false;
}
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
// Set initial tree root to null
this->root = NULL;
}
bool is_k_level_sum(MyQueue queue, int level, int k)
{
if (queue.is_empty() == true)
{
return false;
}
int sum = 0;
QueueNode *temp = queue.front;
//Count number of nodes in given level
while (temp != NULL && temp->level == level)
{
sum += temp->element->data;
temp = temp->next;
}
if (sum == k)
{
return true;
}
else
{
return false;
}
}
//Print all levels which sum is equal to given value
void level_sum(int k)
{
if (this->root == NULL)
{
cout << "\n Empty Binary Tree \n";
}
else
{
//Get top node in tree
TreeNode *node = this->root;
//Create a Queue
MyQueue queue = MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
QueueNode *temp = queue.front;
int level = 0;
//Add tree level
while (temp != NULL)
{
node = temp->element;
level = temp->level;
if (node->left != NULL)
{
//Add left node
queue.enqueue(node->left, level + 1);
}
if (node->right != NULL)
{
//Add right node
queue.enqueue(node->right, level + 1);
}
temp = temp->next;
}
bool status = false;
level = 0;
while (queue.is_empty() == false)
{
level = queue.front->level;
status = this->is_k_level_sum(queue, level, k);
if (status == true)
{
cout << " [";
}
// When level nodes sum is equal to k,
// Then this loop are printed node value and remove level nodes
// Otherwise it's removing current level nodes
while (queue.is_empty() == false && queue.front->level == level)
{
if (status == true)
{
//When sum exist
cout << " " << queue.front->element->data;
}
//remove a queue node
queue.dequeue();
}
if (status == true)
{
cout << " ]\n";
}
}
}
}
};
int main()
{
//Object of Binary Tree
BinaryTree tree = BinaryTree();
tree.root = new TreeNode(10);
tree.root->left = new TreeNode(2);
tree.root->right = new TreeNode(3);
tree.root->right->right = new TreeNode(5);
tree.root->right->left = new TreeNode(1);
tree.root->left->left = new TreeNode(4);
tree.root->left->left->left = new TreeNode(7);
tree.root->left->left->right = new TreeNode(3);
tree.root->right->left->right = new TreeNode(6);
tree.root->right->right->right = new TreeNode(11);
tree.root->right->right->right->left = new TreeNode(-3);
tree.root->left->left->right->left = new TreeNode(5);
tree.root->left->left->right->right = new TreeNode(8);
tree.root->left->left->right->right->left = new TreeNode(-1);
tree.root->left->left->right->right->right = new TreeNode(11);
tree.level_sum(10);
return 0;
}
Output
[ 10 ]
[ 4 1 5 ]
[ 5 8 -3 ]
[ -1 11 ]
//Include namespace system
using System;
/*
C# program
Print all K-sum levels in a Binary Tree
*/
//Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
public TreeNode element;
public QueueNode next;
public int level;
public QueueNode(TreeNode element, int level)
{
this.element = element;
this.next = null;
this.level = level;
}
}
//Define custom queue class
class MyQueue
{
public QueueNode front;
public QueueNode tail;
public MyQueue()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
public void enqueue(TreeNode element, int level)
{
QueueNode new_node = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
//Add node at last position
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
public Boolean is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
public Boolean is_k_level_sum(MyQueue queue, int level, int k)
{
if (queue.is_empty() == true)
{
return false;
}
int sum = 0;
QueueNode temp = queue.front;
//Count number of nodes in given level
while (temp != null && temp.level == level)
{
sum += temp.element.data;
temp = temp.next;
}
if (sum == k)
{
return true;
}
else
{
return false;
}
}
//Print all levels which sum is equal to given value
public void level_sum(int k)
{
if (this.root == null)
{
Console.Write("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
TreeNode node = this.root;
//Create a Queue
MyQueue queue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
QueueNode temp = queue.front;
int level = 0;
//Add tree level
while (temp != null)
{
node = temp.element;
level = temp.level;
if (node.left != null)
{
//Add left node
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
//Add right node
queue.enqueue(node.right, level + 1);
}
temp = temp.next;
}
Boolean status = false;
level = 0;
while (queue.is_empty() == false)
{
level = queue.front.level;
status = is_k_level_sum(queue, level, k);
if (status == true)
{
Console.Write(" [");
}
// When level nodes sum is equal to k,
// Then this loop are printed node value and remove level nodes
// Otherwise it's removing current level nodes
while (queue.is_empty() == false && queue.front.level == level)
{
if (status == true)
{
//When sum exist
Console.Write(" " + queue.front.element.data);
}
//remove a queue node
queue.dequeue();
}
if (status == true)
{
Console.Write(" ]\n");
}
}
}
}
public static void Main(String[] args)
{
//Object of Binary Tree
BinaryTree tree = new BinaryTree();
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(5);
tree.root.right.left = new TreeNode(1);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(3);
tree.root.right.left.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.left = new TreeNode(-3);
tree.root.left.left.right.left = new TreeNode(5);
tree.root.left.left.right.right = new TreeNode(8);
tree.root.left.left.right.right.left = new TreeNode(-1);
tree.root.left.left.right.right.right = new TreeNode(11);
tree.level_sum(10);
}
}
Output
[ 10 ]
[ 4 1 5 ]
[ 5 8 -3 ]
[ -1 11 ]
<?php
/*
Php program
Print all K-sum levels in a Binary Tree
*/
//Binary Tree node
class TreeNode
{
public $data;
public $left;
public $right;
function __construct($data)
{
//set node value
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
// Queue Node
class QueueNode
{
public $element;
public $next;
public $level;
function __construct($element, $level)
{
$this->element = $element;
$this->next = null;
$this->level = $level;
}
}
//Define custom queue class
class MyQueue
{
public $front;
public $tail;
function __construct()
{
$this->front = null;
$this->tail = null;
}
//Add a new node at last of queue
public function enqueue($element, $level)
{
$new_node = new QueueNode($element, $level);
if ($this->front == null)
{
//When first node of queue
$this->front = $new_node;
}
else
{
//Add node at last position
$this->tail->next = $new_node;
}
$this->tail = $new_node;
}
//Delete first node of queue
public function dequeue()
{
if ($this->front != null)
{
if ($this->tail == $this->front)
{
$this->tail = null;
$this->front = null;
}
else
{
$this->front = $this->front->next;
}
}
}
public function is_empty()
{
if ($this->front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
public $root;
function __construct()
{
// Set initial tree root to null
$this->root = null;
}
public function is_k_level_sum($queue, $level, $k)
{
if ($queue->is_empty() == true)
{
return false;
}
$sum = 0;
$temp = $queue->front;
//Count number of nodes in given level
while ($temp != null && $temp->level == $level)
{
$sum += $temp->element->data;
$temp = $temp->next;
}
if ($sum == $k)
{
return true;
}
else
{
return false;
}
}
//Print all levels which sum is equal to given value
public function level_sum($k)
{
if ($this->root == null)
{
echo "\n Empty Binary Tree \n";
}
else
{
//Get top node in tree
$node = $this->root;
//Create a Queue
$queue = new MyQueue();
//Add first node at the level of one
$queue->enqueue($node, 1);
$temp = $queue->front;
$level = 0;
//Add tree level
while ($temp != null)
{
$node = $temp->element;
$level = $temp->level;
if ($node->left != null)
{
//Add left node
$queue->enqueue($node->left, $level + 1);
}
if ($node->right != null)
{
//Add right node
$queue->enqueue($node->right, $level + 1);
}
$temp = $temp->next;
}
$status = false;
$level = 0;
while ($queue->is_empty() == false)
{
$level = $queue->front->level;
$status = $this->is_k_level_sum($queue, $level, $k);
if ($status == true)
{
echo " [";
}
// When level nodes sum is equal to k,
// Then this loop are printed node value and remove level nodes
// Otherwise it's removing current level nodes
while ($queue->is_empty() == false && $queue->front->level == $level)
{
if ($status == true)
{
//When sum exist
echo " ". $queue->front->element->data;
}
//remove a queue node
$queue->dequeue();
}
if ($status == true)
{
echo " ]\n";
}
}
}
}
}
function main()
{
//Object of Binary Tree
$tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/ \
2 3
/ / \
4 1 5
/ \ \ \
7 3 6 11
/ \ /
5 8 -3
/ \
-1 11
-----------------------
*/
//Add node
$tree->root = new TreeNode(10);
$tree->root->left = new TreeNode(2);
$tree->root->right = new TreeNode(3);
$tree->root->right->right = new TreeNode(5);
$tree->root->right->left = new TreeNode(1);
$tree->root->left->left = new TreeNode(4);
$tree->root->left->left->left = new TreeNode(7);
$tree->root->left->left->right = new TreeNode(3);
$tree->root->right->left->right = new TreeNode(6);
$tree->root->right->right->right = new TreeNode(11);
$tree->root->right->right->right->left = new TreeNode(-3);
$tree->root->left->left->right->left = new TreeNode(5);
$tree->root->left->left->right->right = new TreeNode(8);
$tree->root->left->left->right->right->left = new TreeNode(-1);
$tree->root->left->left->right->right->right = new TreeNode(11);
$tree->level_sum(10);
}
main();
Output
[ 10 ]
[ 4 1 5 ]
[ 5 8 -3 ]
[ -1 11 ]
/*
Node Js program
Print all K-sum levels in a Binary Tree
*/
//Binary Tree node
class TreeNode
{
constructor(data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
constructor(element, level)
{
this.element = element;
this.next = null;
this.level = level;
}
}
//Define custom queue class
class MyQueue
{
constructor()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
enqueue(element, level)
{
var new_node = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
//Add node at last position
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
constructor()
{
// Set initial tree root to null
this.root = null;
}
is_k_level_sum(queue, level, k)
{
if (queue.is_empty() == true)
{
return false;
}
var sum = 0;
var temp = queue.front;
//Count number of nodes in given level
while (temp != null && temp.level == level)
{
sum += temp.element.data;
temp = temp.next;
}
if (sum == k)
{
return true;
}
else
{
return false;
}
}
//Print all levels which sum is equal to given value
level_sum(k)
{
if (this.root == null)
{
process.stdout.write("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
var node = this.root;
//Create a Queue
var queue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
var temp = queue.front;
var level = 0;
//Add tree level
while (temp != null)
{
node = temp.element;
level = temp.level;
if (node.left != null)
{
//Add left node
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
//Add right node
queue.enqueue(node.right, level + 1);
}
temp = temp.next;
}
var status = false;
level = 0;
while (queue.is_empty() == false)
{
level = queue.front.level;
status = this.is_k_level_sum(queue, level, k);
if (status == true)
{
process.stdout.write(" [");
}
// When level nodes sum is equal to k,
// Then this loop are printed node value and remove level nodes
// Otherwise it's removing current level nodes
while (queue.is_empty() == false && queue.front.level == level)
{
if (status == true)
{
//When sum exist
process.stdout.write(" " + queue.front.element.data);
}
//remove a queue node
queue.dequeue();
}
if (status == true)
{
process.stdout.write(" ]\n");
}
}
}
}
}
function main()
{
//Object of Binary Tree
var tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/ \
2 3
/ / \
4 1 5
/ \ \ \
7 3 6 11
/ \ /
5 8 -3
/ \
-1 11
-----------------------
*/
//Add node
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(5);
tree.root.right.left = new TreeNode(1);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(3);
tree.root.right.left.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.left = new TreeNode(-3);
tree.root.left.left.right.left = new TreeNode(5);
tree.root.left.left.right.right = new TreeNode(8);
tree.root.left.left.right.right.left = new TreeNode(-1);
tree.root.left.left.right.right.right = new TreeNode(11);
tree.level_sum(10);
}
main();
Output
[ 10 ]
[ 4 1 5 ]
[ 5 8 -3 ]
[ -1 11 ]
# Python 3 program
# Print all K-sum levels in a Binary Tree
# Binary Tree node
class TreeNode :
def __init__(self, data) :
# set node value
self.data = data
self.left = None
self.right = None
# Queue Node
class QueueNode :
def __init__(self, element, level) :
self.element = element
self.next = None
self.level = level
# Define custom queue class
class MyQueue :
def __init__(self) :
self.front = None
self.tail = None
# Add a new node at last of queue
def enqueue(self, element, level) :
new_node = QueueNode(element, level)
if (self.front == None) :
# When first node of queue
self.front = new_node
else :
# Add node at last position
self.tail.next = new_node
self.tail = new_node
# Delete first node of queue
def dequeue(self) :
if (self.front != None) :
if (self.tail == self.front) :
self.tail = None
self.front = None
else :
self.front = self.front.next
def is_empty(self) :
if (self.front == None) :
return True
else :
return False
class BinaryTree :
def __init__(self) :
# Set initial tree root to null
self.root = None
def is_k_level_sum(self, queue, level, k) :
if (queue.is_empty() == True) :
return False
sum = 0
temp = queue.front
# Count number of nodes in given level
while (temp != None and temp.level == level) :
sum += temp.element.data
temp = temp.next
if (sum == k) :
return True
else :
return False
# Print all levels which sum is equal to given value
def level_sum(self, k) :
if (self.root == None) :
print("\n Empty Binary Tree \n", end = "")
else :
# Get top node in tree
node = self.root
# Create a Queue
queue = MyQueue()
# Add first node at the level of one
queue.enqueue(node, 1)
temp = queue.front
level = 0
# Add tree level
while (temp != None) :
node = temp.element
level = temp.level
if (node.left != None) :
# Add left node
queue.enqueue(node.left, level + 1)
if (node.right != None) :
# Add right node
queue.enqueue(node.right, level + 1)
temp = temp.next
status = False
level = 0
while (queue.is_empty() == False) :
level = queue.front.level
status = self.is_k_level_sum(queue, level, k)
if (status == True) :
print(" [", end = "")
# When level nodes sum is equal to k,
# Then this loop are printed node value and remove level nodes
# Otherwise it's removing current level nodes
while (queue.is_empty() == False and queue.front.level == level) :
if (status == True) :
# When sum exist
print(" ", queue.front.element.data, end = "")
# remove a queue node
queue.dequeue()
if (status == True) :
print(" ]\n", end = "")
def main() :
# Object of Binary Tree
tree = BinaryTree()
#
# Construct Binary Tree
# -----------------------
# 10
# / \
# 2 3
# / / \
# 4 1 5
# / \ \ \
# 7 3 6 11
# / \ /
# 5 8 -3
# / \
# -1 11
# -----------------------
#
# Add node
tree.root = TreeNode(10)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.right.right = TreeNode(5)
tree.root.right.left = TreeNode(1)
tree.root.left.left = TreeNode(4)
tree.root.left.left.left = TreeNode(7)
tree.root.left.left.right = TreeNode(3)
tree.root.right.left.right = TreeNode(6)
tree.root.right.right.right = TreeNode(11)
tree.root.right.right.right.left = TreeNode(-3)
tree.root.left.left.right.left = TreeNode(5)
tree.root.left.left.right.right = TreeNode(8)
tree.root.left.left.right.right.left = TreeNode(-1)
tree.root.left.left.right.right.right = TreeNode(11)
tree.level_sum(10)
if __name__ == "__main__": main()
Output
[ 10 ]
[ 4 1 5 ]
[ 5 8 -3 ]
[ -1 11 ]
# Ruby program
# Print all K-sum levels in a Binary Tree
# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# set node value
self.data = data
self.left = nil
self.right = nil
end
end
# Queue Node
class QueueNode
# Define the accessor and reader of class QueueNode
attr_reader :element, :next, :level
attr_accessor :element, :next, :level
def initialize(element, level)
self.element = element
self.next = nil
self.level = level
end
end
# Define custom queue class
class MyQueue
# Define the accessor and reader of class MyQueue
attr_reader :front, :tail
attr_accessor :front, :tail
def initialize()
self.front = nil
self.tail = nil
end
# Add a new node at last of queue
def enqueue(element, level)
new_node = QueueNode.new(element, level)
if (self.front == nil)
# When first node of queue
self.front = new_node
else
# Add node at last position
self.tail.next = new_node
end
self.tail = new_node
end
# Delete first node of queue
def dequeue()
if (self.front != nil)
if (self.tail == self.front)
self.tail = nil
self.front = nil
else
self.front = self.front.next
end
end
end
def is_empty()
if (self.front == nil)
return true
else
return false
end
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
# Set initial tree root to null
self.root = nil
end
def is_k_level_sum(queue, level, k)
if (queue.is_empty() == true)
return false
end
sum = 0
temp = queue.front
# Count number of nodes in given level
while (temp != nil && temp.level == level)
sum += temp.element.data
temp = temp.next
end
if (sum == k)
return true
else
return false
end
end
# Print all levels which sum is equal to given value
def level_sum(k)
if (self.root == nil)
print("\n Empty Binary Tree \n")
else
# Get top node in tree
node = self.root
# Create a Queue
queue = MyQueue.new()
# Add first node at the level of one
queue.enqueue(node, 1)
temp = queue.front
level = 0
# Add tree level
while (temp != nil)
node = temp.element
level = temp.level
if (node.left != nil)
# Add left node
queue.enqueue(node.left, level + 1)
end
if (node.right != nil)
# Add right node
queue.enqueue(node.right, level + 1)
end
temp = temp.next
end
status = false
level = 0
while (queue.is_empty() == false)
level = queue.front.level
status = self.is_k_level_sum(queue, level, k)
if (status == true)
print(" [")
end
# When level nodes sum is equal to k,
# Then this loop are printed node value and remove level nodes
# Otherwise it's removing current level nodes
while (queue.is_empty() == false && queue.front.level == level)
if (status == true)
# When sum exist
print(" ", queue.front.element.data)
end
# remove a queue node
queue.dequeue()
end
if (status == true)
print(" ]\n")
end
end
end
end
end
def main()
# Object of Binary Tree
tree = BinaryTree.new()
#
# Construct Binary Tree
# -----------------------
# 10
# / \
# 2 3
# / / \
# 4 1 5
# / \ \ \
# 7 3 6 11
# / \ /
# 5 8 -3
# / \
# -1 11
# -----------------------
#
# Add node
tree.root = TreeNode.new(10)
tree.root.left = TreeNode.new(2)
tree.root.right = TreeNode.new(3)
tree.root.right.right = TreeNode.new(5)
tree.root.right.left = TreeNode.new(1)
tree.root.left.left = TreeNode.new(4)
tree.root.left.left.left = TreeNode.new(7)
tree.root.left.left.right = TreeNode.new(3)
tree.root.right.left.right = TreeNode.new(6)
tree.root.right.right.right = TreeNode.new(11)
tree.root.right.right.right.left = TreeNode.new(-3)
tree.root.left.left.right.left = TreeNode.new(5)
tree.root.left.left.right.right = TreeNode.new(8)
tree.root.left.left.right.right.left = TreeNode.new(-1)
tree.root.left.left.right.right.right = TreeNode.new(11)
tree.level_sum(10)
end
main()
Output
[ 10 ]
[ 4 1 5 ]
[ 5 8 -3 ]
[ -1 11 ]
/*
Scala program
Print all K-sum levels in a Binary Tree
*/
//Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
// Queue Node
class QueueNode(var element: TreeNode,
var next: QueueNode,
var level: Int)
{
def this(element: TreeNode, level: Int)
{
this(element, null, level);
}
}
//Define custom queue class
class MyQueue(var front: QueueNode,
var tail: QueueNode)
{
def this()
{
this(null, null);
}
//Add a new node at last of queue
def enqueue(element: TreeNode, level: Int): Unit = {
var new_node: QueueNode = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
//Add node at last position
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
def dequeue(): Unit = {
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
def is_empty(): Boolean = {
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def is_k_level_sum(queue: MyQueue, level: Int, k: Int): Boolean = {
if (queue.is_empty() == true)
{
return false;
}
var sum: Int = 0;
var temp: QueueNode = queue.front;
//Count number of nodes in given level
while (temp != null && temp.level == level)
{
sum += temp.element.data;
temp = temp.next;
}
if (sum == k)
{
return true;
}
else
{
return false;
}
}
//Print all levels which sum is equal to given value
def level_sum(k: Int): Unit = {
if (this.root == null)
{
print("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
var node: TreeNode = this.root;
//Create a Queue
var queue: MyQueue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
var temp: QueueNode = queue.front;
var level: Int = 0;
//Add tree level
while (temp != null)
{
node = temp.element;
level = temp.level;
if (node.left != null)
{
//Add left node
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
//Add right node
queue.enqueue(node.right, level + 1);
}
temp = temp.next;
}
var status: Boolean = false;
level = 0;
while (queue.is_empty() == false)
{
level = queue.front.level;
status = is_k_level_sum(queue, level, k);
if (status == true)
{
print(" [");
}
// When level nodes sum is equal to k,
// Then this loop are printed node value and remove level nodes
// Otherwise it's removing current level nodes
while (queue.is_empty() == false && queue.front.level == level)
{
if (status == true)
{
//When sum exist
print(" " + queue.front.element.data);
}
//remove a queue node
queue.dequeue();
}
if (status == true)
{
print(" ]\n");
}
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Object of Binary Tree
var tree: BinaryTree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/ \
2 3
/ / \
4 1 5
/ \ \ \
7 3 6 11
/ \ /
5 8 -3
/ \
-1 11
-----------------------
*/
//Add node
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(5);
tree.root.right.left = new TreeNode(1);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(3);
tree.root.right.left.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.left = new TreeNode(-3);
tree.root.left.left.right.left = new TreeNode(5);
tree.root.left.left.right.right = new TreeNode(8);
tree.root.left.left.right.right.left = new TreeNode(-1);
tree.root.left.left.right.right.right = new TreeNode(11);
tree.level_sum(10);
}
}
Output
[ 10 ]
[ 4 1 5 ]
[ 5 8 -3 ]
[ -1 11 ]
/*
Swift 4 program
Print all K-sum levels in a Binary Tree
*/
//Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
//set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
// Queue Node
class QueueNode
{
var element: TreeNode? ;
var next: QueueNode? ;
var level: Int;
init(_ element: TreeNode? , _ level : Int)
{
self.element = element;
self.next = nil;
self.level = level;
}
}
//Define custom queue class
class MyQueue
{
var front: QueueNode? ;
var tail: QueueNode? ;
init()
{
self.front = nil;
self.tail = nil;
}
//Add a new node at last of queue
func enqueue(_ element: TreeNode? , _ level : Int)
{
let new_node: QueueNode? = QueueNode(element, level);
if (self.front == nil)
{
//When first node of queue
self.front = new_node;
}
else
{
//Add node at last position
self.tail!.next = new_node;
}
self.tail = new_node;
}
//Delete first node of queue
func dequeue()
{
if (self.front != nil)
{
if (self.tail === self.front)
{
self.tail = nil;
self.front = nil;
}
else
{
self.front = self.front!.next;
}
}
}
func is_empty() -> Bool
{
if (self.front == nil)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
// Set initial tree root to null
self.root = nil;
}
func is_k_level_sum(_ queue: MyQueue, _ level: Int, _ k: Int) -> Bool
{
if (queue.is_empty() == true)
{
return false;
}
var sum: Int = 0;
var temp: QueueNode? = queue.front;
//Count number of nodes in given level
while (temp != nil && temp!.level == level)
{
sum += temp!.element!.data;
temp = temp!.next;
}
if (sum == k)
{
return true;
}
else
{
return false;
}
}
//Print all levels which sum is equal to given value
func level_sum(_ k: Int)
{
if (self.root == nil)
{
print("\n Empty Binary Tree \n", terminator: "");
}
else
{
//Get top node in tree
var node: TreeNode? = self.root;
//Create a Queue
let queue: MyQueue = MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
var temp: QueueNode? = queue.front;
var level: Int = 0;
//Add tree level
while (temp != nil)
{
node = temp!.element;
level = temp!.level;
if (node!.left != nil)
{
//Add left node
queue.enqueue(node!.left, level + 1);
}
if (node!.right != nil)
{
//Add right node
queue.enqueue(node!.right, level + 1);
}
temp = temp!.next;
}
var status: Bool = false;
level = 0;
while (queue.is_empty() == false)
{
level = queue.front!.level;
status = self.is_k_level_sum(queue, level, k);
if (status == true)
{
print(" [", terminator: "");
}
// When level nodes sum is equal to k,
// Then this loop are printed node value and remove level nodes
// Otherwise it"s removing current level nodes
while (queue.is_empty() == false && queue.front!.level == level)
{
if (status == true)
{
//When sum exist
print(" ", queue.front!.element!.data, terminator: "");
}
//remove a queue node
queue.dequeue();
}
if (status == true)
{
print(" ]\n", terminator: "");
}
}
}
}
}
func main()
{
//Object of Binary Tree
let tree: BinaryTree = BinaryTree();
tree.root = TreeNode(10);
tree.root!.left = TreeNode(2);
tree.root!.right = TreeNode(3);
tree.root!.right!.right = TreeNode(5);
tree.root!.right!.left = TreeNode(1);
tree.root!.left!.left = TreeNode(4);
tree.root!.left!.left!.left = TreeNode(7);
tree.root!.left!.left!.right = TreeNode(3);
tree.root!.right!.left!.right = TreeNode(6);
tree.root!.right!.right!.right = TreeNode(11);
tree.root!.right!.right!.right!.left = TreeNode(-3);
tree.root!.left!.left!.right!.left = TreeNode(5);
tree.root!.left!.left!.right!.right = TreeNode(8);
tree.root!.left!.left!.right!.right!.left = TreeNode(-1);
tree.root!.left!.left!.right!.right!.right = TreeNode(11);
tree.level_sum(10);
}
main();
Output
[ 10 ]
[ 4 1 5 ]
[ 5 8 -3 ]
[ -1 11 ]
Output Explanation
The code implements the algorithm and prints the levels of the binary tree where the sum of nodes' values is equal to the given K. It displays the nodes' values for each level in square brackets.
Time Complexity
The time complexity of this algorithm is O(N), where N is the number of nodes in the binary tree. This is because we perform a BFS traversal through all nodes of the binary tree. The space complexity is also O(N), as we use a queue for BFS traversal.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment