Level sum of bitwise and operation in binary tree
Here given code implementation process.
/*
Java program for
Level sum of bitwise and operation in 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 QNode
{
public TreeNode n;
public QNode next;
public int level;
public QNode(TreeNode n, int level)
{
this.n = n;
this.next = null;
this.level = level;
}
}
// Define custom queue class
class MyQueue
{
public QNode front;
public QNode rear;
public int size;
public MyQueue()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
public void enqueue(TreeNode n, int level)
{
QNode node = new QNode(n, level);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size++;
this.rear = node;
}
// Delete front node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size--;
}
}
public int isSize()
{
return this.size;
}
public boolean isEmpty()
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
public QNode peek()
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front;
}
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
public void levelAndSum()
{
if (this.root == null)
{
return;
}
// Auxiliary variables
int sum = 0;
int level = 0;
int current = -1;
int auxiliary = 0;
MyQueue q = new MyQueue();
// Add first value of queue
q.enqueue(this.root, level);
while (!q.isEmpty())
{
QNode node = q.peek();
// Remove queue element
q.dequeue();
if (node.level != current)
{
System.out.print("\n");
// Change current level
current = node.level;
// Add previous level result
sum += auxiliary;
// Get first node of current level
auxiliary = node.n.data;
}
else
{
// Perform And operation
auxiliary = auxiliary & node.n.data;
}
// Display the level node
System.out.print(" " + node.n.data);
if (node.n.left != null)
{
// Add left node
q.enqueue(node.n.left, node.level + 1);
}
if (node.n.right != null)
{
// Add right node
q.enqueue(node.n.right, node.level + 1);
}
}
// Add last level result
sum += auxiliary;
System.out.println("\n Result : " + sum);
}
public static void main(String[] args)
{
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Construct Tree 1
*/
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(19);
tree1.root.left.right = new TreeNode(7);
tree1.root.left.left = new TreeNode(11);
tree1.root.right.right.left = new TreeNode(-2);
/*
3
/ \
2 7
/ \
7 8
-----------------
Construct Tree 2
*/
tree2.root = new TreeNode(3);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(7);
tree2.root.left.right = new TreeNode(8);
tree2.root.left.left = new TreeNode(7);
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Tree 1
-----------------
1 1 = 1
/ \
2 7 2 & 7 = 2
/ \ \
11 7 19 11 & 7 & 19 = 3
/
-2 -2 = -2
-----------------------------------------
1 + 2 + 3 -2 = 4
*/
tree1.levelAndSum();
/*
3
/ \
2 7
/ \
7 8
-----------------
Tree 2
----------------
3 3 = 3
/ \
2 7 2 & 7 = 2
/ \
7 8 7 & 8 = 0
-----------------------------------------
3 + 2 + 0 = 5
*/
tree2.levelAndSum();
}
}
Output
1
2 7
11 7 19
-2
Result : 4
3
2 7
7 8
Result : 5
// Include header file
#include <iostream>
using namespace std;
/*
C++ program for
Level sum of bitwise and operation in 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 QNode
{
public:
TreeNode *n;
QNode *next;
int level;
QNode(TreeNode *n, int level)
{
this->n = n;
this->next = NULL;
this->level = level;
}
};
// Define custom queue class
class MyQueue
{
public:
QNode *front;
QNode *rear;
int size;
MyQueue()
{
this->front = NULL;
this->rear = NULL;
this->size = 0;
}
// Add a new node at last of queue
void enqueue(TreeNode *n, int level)
{
QNode *node = new QNode(n, level);
if (this->front == NULL)
{
// When first node of queue
this->front = node;
}
else
{
// Add node at last level
this->rear->next = node;
}
this->size++;
this->rear = node;
}
// Delete front node of queue
void dequeue()
{
if (this->front != NULL)
{
if (this->rear == this->front)
{
this->rear = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
}
this->size--;
}
}
int isSize()
{
return this->size;
}
bool isEmpty()
{
if (this->isSize() == 0)
{
return true;
}
return false;
}
QNode *peek()
{
if (this->isSize() == 0)
{
return NULL;
}
else
{
return this->front;
}
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
void levelAndSum()
{
if (this->root == NULL)
{
return;
}
// Auxiliary variables
int sum = 0;
int level = 0;
int current = -1;
int auxiliary = 0;
MyQueue *q = new MyQueue();
// Add first value of queue
q->enqueue(this->root, level);
while (!q->isEmpty())
{
QNode *node = q->peek();
// Remove queue element
q->dequeue();
if (node->level != current)
{
cout << "\n";
// Change current level
current = node->level;
// Add previous level result
sum += auxiliary;
// Get first node of current level
auxiliary = node->n->data;
}
else
{
// Perform And operation
auxiliary = auxiliary &node->n->data;
}
// Display the level node
cout << " " << node->n->data;
if (node->n->left != NULL)
{
// Add left node
q->enqueue(node->n->left, node->level + 1);
}
if (node->n->right != NULL)
{
// Add right node
q->enqueue(node->n->right, node->level + 1);
}
}
// Add last level result
sum += auxiliary;
cout << "\n Result : " << sum << endl;
}
};
int main()
{
BinaryTree *tree1 = new BinaryTree();
BinaryTree *tree2 = new BinaryTree();
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Construct Tree 1
*/
tree1->root = new TreeNode(1);
tree1->root->left = new TreeNode(2);
tree1->root->right = new TreeNode(7);
tree1->root->right->right = new TreeNode(19);
tree1->root->left->right = new TreeNode(7);
tree1->root->left->left = new TreeNode(11);
tree1->root->right->right->left = new TreeNode(-2);
/*
3
/ \
2 7
/ \
7 8
-----------------
Construct Tree 2
*/
tree2->root = new TreeNode(3);
tree2->root->left = new TreeNode(2);
tree2->root->right = new TreeNode(7);
tree2->root->left->right = new TreeNode(8);
tree2->root->left->left = new TreeNode(7);
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Tree 1
-----------------
1 1 = 1
/ \
2 7 2 & 7 = 2
/ \ \
11 7 19 11 & 7 & 19 = 3
/
-2 -2 = -2
-----------------------------------------
1 + 2 + 3 -2 = 4
*/
tree1->levelAndSum();
/*
3
/ \
2 7
/ \
7 8
-----------------
Tree 2
----------------
3 3 = 3
/ \
2 7 2 & 7 = 2
/ \
7 8 7 & 8 = 0
-----------------------------------------
3 + 2 + 0 = 5
*/
tree2->levelAndSum();
return 0;
}
Output
1
2 7
11 7 19
-2
Result : 4
3
2 7
7 8
Result : 5
// Include namespace system
using System;
/*
Csharp program for
Level sum of bitwise and operation in binary tree
*/
// Binary Tree node
public 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
public class QNode
{
public TreeNode n;
public QNode next;
public int level;
public QNode(TreeNode n, int level)
{
this.n = n;
this.next = null;
this.level = level;
}
}
// Define custom queue class
public class MyQueue
{
public QNode front;
public QNode rear;
public int size;
public MyQueue()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
public void enqueue(TreeNode n, int level)
{
QNode node = new QNode(n, level);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size++;
this.rear = node;
}
// Delete front node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size--;
}
}
public int isSize()
{
return this.size;
}
public Boolean isEmpty()
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
public QNode peek()
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front;
}
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
public void levelAndSum()
{
if (this.root == null)
{
return;
}
// Auxiliary variables
int sum = 0;
int level = 0;
int current = -1;
int auxiliary = 0;
MyQueue q = new MyQueue();
// Add first value of queue
q.enqueue(this.root, level);
while (!q.isEmpty())
{
QNode node = q.peek();
// Remove queue element
q.dequeue();
if (node.level != current)
{
Console.Write("\n");
// Change current level
current = node.level;
// Add previous level result
sum += auxiliary;
// Get first node of current level
auxiliary = node.n.data;
}
else
{
// Perform And operation
auxiliary = auxiliary & node.n.data;
}
// Display the level node
Console.Write(" " + node.n.data);
if (node.n.left != null)
{
// Add left node
q.enqueue(node.n.left, node.level + 1);
}
if (node.n.right != null)
{
// Add right node
q.enqueue(node.n.right, node.level + 1);
}
}
// Add last level result
sum += auxiliary;
Console.WriteLine("\n Result : " + sum);
}
public static void Main(String[] args)
{
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Construct Tree 1
*/
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(19);
tree1.root.left.right = new TreeNode(7);
tree1.root.left.left = new TreeNode(11);
tree1.root.right.right.left = new TreeNode(-2);
/*
3
/ \
2 7
/ \
7 8
-----------------
Construct Tree 2
*/
tree2.root = new TreeNode(3);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(7);
tree2.root.left.right = new TreeNode(8);
tree2.root.left.left = new TreeNode(7);
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Tree 1
-----------------
1 1 = 1
/ \
2 7 2 & 7 = 2
/ \ \
11 7 19 11 & 7 & 19 = 3
/
-2 -2 = -2
-----------------------------------------
1 + 2 + 3 -2 = 4
*/
tree1.levelAndSum();
/*
3
/ \
2 7
/ \
7 8
-----------------
Tree 2
----------------
3 3 = 3
/ \
2 7 2 & 7 = 2
/ \
7 8 7 & 8 = 0
-----------------------------------------
3 + 2 + 0 = 5
*/
tree2.levelAndSum();
}
}
Output
1
2 7
11 7 19
-2
Result : 4
3
2 7
7 8
Result : 5
package main
import "fmt"
/*
Go program for
Level sum of bitwise and operation in binary tree
*/
// Binary Tree node
type TreeNode struct {
data int
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
// Set node value
me.data = data
me.left = nil
me.right = nil
return me
}
// Queue Node
type QNode struct {
n * TreeNode
next * QNode
level int
}
func getQNode(n * TreeNode, level int) * QNode {
var me *QNode = &QNode {}
me.n = n
me.next = nil
me.level = level
return me
}
// Define custom queue class
type MyQueue struct {
front * QNode
rear * QNode
size int
}
func getMyQueue() * MyQueue {
var me *MyQueue = &MyQueue {}
me.front = nil
me.rear = nil
me.size = 0
return me
}
// Add a new node at last of queue
func(this *MyQueue) enqueue(n * TreeNode, level int) {
var node * QNode = getQNode(n, level)
if this.front == nil {
// When first node of queue
this.front = node
} else {
// Add node at last level
this.rear.next = node
}
this.size++
this.rear = node
}
// Delete front node of queue
func(this *MyQueue) dequeue() {
if this.front != nil {
if this.rear == this.front {
this.rear = nil
this.front = nil
} else {
this.front = this.front.next
}
this.size--
}
}
func(this MyQueue) isSize() int {
return this.size
}
func(this MyQueue) isEmpty() bool {
if this.isSize() == 0 {
return true
}
return false
}
func(this MyQueue) peek() * QNode {
if this.isSize() == 0 {
return nil
} else {
return this.front
}
}
type BinaryTree struct {
root * TreeNode
}
func getBinaryTree() * BinaryTree {
var me *BinaryTree = &BinaryTree {}
// Set initial value
me.root = nil
return me
}
func(this BinaryTree) levelAndSum() {
if this.root == nil {
return
}
// Auxiliary variables
var sum int = 0
var level int = 0
var current int = -1
var auxiliary int = 0
var q * MyQueue = getMyQueue()
// Add first value of queue
q.enqueue(this.root, level)
for (!q.isEmpty()) {
var node * QNode = q.peek()
// Remove queue element
q.dequeue()
if node.level != current {
fmt.Print("\n")
// Change current level
current = node.level
// Add previous level result
sum += auxiliary
// Get first node of current level
auxiliary = node.n.data
} else {
// Perform And operation
auxiliary = auxiliary & node.n.data
}
// Display the level node
fmt.Print(" ", node.n.data)
if node.n.left != nil {
// Add left node
q.enqueue(node.n.left, node.level + 1)
}
if node.n.right != nil {
// Add right node
q.enqueue(node.n.right, node.level + 1)
}
}
// Add last level result
sum += auxiliary
fmt.Println("\n Result : ", sum)
}
func main() {
var tree1 * BinaryTree = getBinaryTree()
var tree2 * BinaryTree = getBinaryTree()
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Construct Tree 1
*/
tree1.root = getTreeNode(1)
tree1.root.left = getTreeNode(2)
tree1.root.right = getTreeNode(7)
tree1.root.right.right = getTreeNode(19)
tree1.root.left.right = getTreeNode(7)
tree1.root.left.left = getTreeNode(11)
tree1.root.right.right.left = getTreeNode(-2)
/*
3
/ \
2 7
/ \
7 8
-----------------
Construct Tree 2
*/
tree2.root = getTreeNode(3)
tree2.root.left = getTreeNode(2)
tree2.root.right = getTreeNode(7)
tree2.root.left.right = getTreeNode(8)
tree2.root.left.left = getTreeNode(7)
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Tree 1
-----------------
1 1 = 1
/ \
2 7 2 & 7 = 2
/ \ \
11 7 19 11 & 7 & 19 = 3
/
-2 -2 = -2
-----------------------------------------
1 + 2 + 3 -2 = 4
*/
tree1.levelAndSum()
/*
3
/ \
2 7
/ \
7 8
-----------------
Tree 2
----------------
3 3 = 3
/ \
2 7 2 & 7 = 2
/ \
7 8 7 & 8 = 0
-----------------------------------------
3 + 2 + 0 = 5
*/
tree2.levelAndSum()
}
Output
1
2 7
11 7 19
-2
Result : 4
3
2 7
7 8
Result : 5
<?php
/*
Php program for
Level sum of bitwise and operation in binary tree
*/
// Binary Tree node
class TreeNode
{
public $data;
public $left;
public $right;
public function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
}
// Queue Node
class QNode
{
public $n;
public $next;
public $level;
public function __construct($n, $level)
{
$this->n = $n;
$this->next = NULL;
$this->level = $level;
}
}
// Define custom queue class
class MyQueue
{
public $front;
public $rear;
public $size;
public function __construct()
{
$this->front = NULL;
$this->rear = NULL;
$this->size = 0;
}
// Add a new node at last of queue
public function enqueue($n, $level)
{
$node = new QNode($n, $level);
if ($this->front == NULL)
{
// When first node of queue
$this->front = $node;
}
else
{
// Add node at last level
$this->rear->next = $node;
}
$this->size++;
$this->rear = $node;
}
// Delete front node of queue
public function dequeue()
{
if ($this->front != NULL)
{
if ($this->rear == $this->front)
{
$this->rear = NULL;
$this->front = NULL;
}
else
{
$this->front = $this->front->next;
}
$this->size--;
}
}
public function isSize()
{
return $this->size;
}
public function isEmpty()
{
if ($this->isSize() == 0)
{
return true;
}
return false;
}
public function peek()
{
if ($this->isSize() == 0)
{
return NULL;
}
else
{
return $this->front;
}
}
}
class BinaryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
public function levelAndSum()
{
if ($this->root == NULL)
{
return;
}
// Auxiliary variables
$sum = 0;
$level = 0;
$current = -1;
$auxiliary = 0;
$q = new MyQueue();
// Add first value of queue
$q->enqueue($this->root, $level);
while (!$q->isEmpty())
{
$node = $q->peek();
// Remove queue element
$q->dequeue();
if ($node->level != $current)
{
echo("\n");
// Change current level
$current = $node->level;
// Add previous level result
$sum += $auxiliary;
// Get first node of current level
$auxiliary = $node->n->data;
}
else
{
// Perform And operation
$auxiliary = $auxiliary & $node->n->data;
}
// Display the level node
echo(" ".$node->n->data);
if ($node->n->left != NULL)
{
// Add left node
$q->enqueue($node->n->left, $node->level + 1);
}
if ($node->n->right != NULL)
{
// Add right node
$q->enqueue($node->n->right, $node->level + 1);
}
}
// Add last level result
$sum += $auxiliary;
echo("\n Result : ".$sum.
"\n");
}
}
function main()
{
$tree1 = new BinaryTree();
$tree2 = new BinaryTree();
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Construct Tree 1
*/
$tree1->root = new TreeNode(1);
$tree1->root->left = new TreeNode(2);
$tree1->root->right = new TreeNode(7);
$tree1->root->right->right = new TreeNode(19);
$tree1->root->left->right = new TreeNode(7);
$tree1->root->left->left = new TreeNode(11);
$tree1->root->right->right->left = new TreeNode(-2);
/*
3
/ \
2 7
/ \
7 8
-----------------
Construct Tree 2
*/
$tree2->root = new TreeNode(3);
$tree2->root->left = new TreeNode(2);
$tree2->root->right = new TreeNode(7);
$tree2->root->left->right = new TreeNode(8);
$tree2->root->left->left = new TreeNode(7);
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Tree 1
-----------------
1 1 = 1
/ \
2 7 2 & 7 = 2
/ \ \
11 7 19 11 & 7 & 19 = 3
/
-2 -2 = -2
-----------------------------------------
1 + 2 + 3 -2 = 4
*/
$tree1->levelAndSum();
/*
3
/ \
2 7
/ \
7 8
-----------------
Tree 2
----------------
3 3 = 3
/ \
2 7 2 & 7 = 2
/ \
7 8 7 & 8 = 0
-----------------------------------------
3 + 2 + 0 = 5
*/
$tree2->levelAndSum();
}
main();
Output
1
2 7
11 7 19
-2
Result : 4
3
2 7
7 8
Result : 5
/*
Node JS program for
Level sum of bitwise and operation in binary tree
*/
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QNode
{
constructor(n, level)
{
this.n = n;
this.next = null;
this.level = level;
}
}
// Define custom queue class
class MyQueue
{
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
enqueue(n, level)
{
var node = new QNode(n, level);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size++;
this.rear = node;
}
// Delete front node of queue
dequeue()
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size--;
}
}
isSize()
{
return this.size;
}
isEmpty()
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
peek()
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front;
}
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
levelAndSum()
{
if (this.root == null)
{
return;
}
// Auxiliary variables
var sum = 0;
var level = 0;
var current = -1;
var auxiliary = 0;
var q = new MyQueue();
// Add first value of queue
q.enqueue(this.root, level);
while (!q.isEmpty())
{
var node = q.peek();
// Remove queue element
q.dequeue();
if (node.level != current)
{
process.stdout.write("\n");
// Change current level
current = node.level;
// Add previous level result
sum += auxiliary;
// Get first node of current level
auxiliary = node.n.data;
}
else
{
// Perform And operation
auxiliary = auxiliary & node.n.data;
}
// Display the level node
process.stdout.write(" " + node.n.data);
if (node.n.left != null)
{
// Add left node
q.enqueue(node.n.left, node.level + 1);
}
if (node.n.right != null)
{
// Add right node
q.enqueue(node.n.right, node.level + 1);
}
}
// Add last level result
sum += auxiliary;
console.log("\n Result : " + sum);
}
}
function main()
{
var tree1 = new BinaryTree();
var tree2 = new BinaryTree();
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Construct Tree 1
*/
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(19);
tree1.root.left.right = new TreeNode(7);
tree1.root.left.left = new TreeNode(11);
tree1.root.right.right.left = new TreeNode(-2);
/*
3
/ \
2 7
/ \
7 8
-----------------
Construct Tree 2
*/
tree2.root = new TreeNode(3);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(7);
tree2.root.left.right = new TreeNode(8);
tree2.root.left.left = new TreeNode(7);
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Tree 1
-----------------
1 1 = 1
/ \
2 7 2 & 7 = 2
/ \ \
11 7 19 11 & 7 & 19 = 3
/
-2 -2 = -2
-----------------------------------------
1 + 2 + 3 -2 = 4
*/
tree1.levelAndSum();
/*
3
/ \
2 7
/ \
7 8
-----------------
Tree 2
----------------
3 3 = 3
/ \
2 7 2 & 7 = 2
/ \
7 8 7 & 8 = 0
-----------------------------------------
3 + 2 + 0 = 5
*/
tree2.levelAndSum();
}
main();
Output
1
2 7
11 7 19
-2
Result : 4
3
2 7
7 8
Result : 5
# Python 3 program for
# Level sum of bitwise and operation in 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 QNode :
def __init__(self, n, level) :
self.n = n
self.next = None
self.level = level
# Define custom queue class
class MyQueue :
def __init__(self) :
self.front = None
self.rear = None
self.size = 0
# Add a new node at last of queue
def enqueue(self, n, level) :
node = QNode(n, level)
if (self.front == None) :
# When first node of queue
self.front = node
else :
# Add node at last level
self.rear.next = node
self.size += 1
self.rear = node
# Delete front node of queue
def dequeue(self) :
if (self.front != None) :
if (self.rear == self.front) :
self.rear = None
self.front = None
else :
self.front = self.front.next
self.size -= 1
def isSize(self) :
return self.size
def isEmpty(self) :
if (self.isSize() == 0) :
return True
return False
def peek(self) :
if (self.isSize() == 0) :
return None
else :
return self.front
class BinaryTree :
def __init__(self) :
self.root = None
def levelAndSum(self) :
if (self.root == None) :
return
# Auxiliary variables
sum = 0
level = 0
current = -1
auxiliary = 0
q = MyQueue()
# Add first value of queue
q.enqueue(self.root, level)
while (not q.isEmpty()) :
node = q.peek()
# Remove queue element
q.dequeue()
if (node.level != current) :
print(end = "\n")
# Change current level
current = node.level
# Add previous level result
sum += auxiliary
# Get first node of current level
auxiliary = node.n.data
else :
# Perform And operation
auxiliary = auxiliary & node.n.data
# Display the level node
print(" ", node.n.data, end = "")
if (node.n.left != None) :
# Add left node
q.enqueue(node.n.left, node.level + 1)
if (node.n.right != None) :
# Add right node
q.enqueue(node.n.right, node.level + 1)
# Add last level result
sum += auxiliary
print("\n Result : ", sum)
def main() :
tree1 = BinaryTree()
tree2 = BinaryTree()
# 1
# / \
# 2 7
# / \ \
# 11 7 19
# /
# -2
# -----------------
# Construct Tree 1
tree1.root = TreeNode(1)
tree1.root.left = TreeNode(2)
tree1.root.right = TreeNode(7)
tree1.root.right.right = TreeNode(19)
tree1.root.left.right = TreeNode(7)
tree1.root.left.left = TreeNode(11)
tree1.root.right.right.left = TreeNode(-2)
# 3
# / \
# 2 7
# / \
# 7 8
# -----------------
# Construct Tree 2
tree2.root = TreeNode(3)
tree2.root.left = TreeNode(2)
tree2.root.right = TreeNode(7)
tree2.root.left.right = TreeNode(8)
tree2.root.left.left = TreeNode(7)
# 1
# / \
# 2 7
# / \ \
# 11 7 19
# /
# -2
# -----------------
# Tree 1
# -----------------
# 1 1 = 1
# / \
# 2 7 2 & 7 = 2
# / \ \
# 11 7 19 11 & 7 & 19 = 3
# /
# -2 -2 = -2
# -----------------------------------------
# 1 + 2 + 3 -2 = 4
tree1.levelAndSum()
# 3
# / \
# 2 7
# / \
# 7 8
# -----------------
# Tree 2
# ----------------
# 3 3 = 3
# / \
# 2 7 2 & 7 = 2
# / \
# 7 8 7 & 8 = 0
# -----------------------------------------
# 3 + 2 + 0 = 5
tree2.levelAndSum()
if __name__ == "__main__": main()
Output
1
2 7
11 7 19
-2
Result : 4
3
2 7
7 8
Result : 5
# Ruby program for
# Level sum of bitwise and operation in 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 QNode
# Define the accessor and reader of class QNode
attr_reader :n, :next, :level
attr_accessor :n, :next, :level
def initialize(n, level)
self.n = n
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, :rear, :size
attr_accessor :front, :rear, :size
def initialize()
self.front = nil
self.rear = nil
self.size = 0
end
# Add a new node at last of queue
def enqueue(n, level)
node = QNode.new(n, level)
if (self.front == nil)
# When first node of queue
self.front = node
else
# Add node at last level
self.rear.next = node
end
self.size += 1
self.rear = node
end
# Delete front node of queue
def dequeue()
if (self.front != nil)
if (self.rear == self.front)
self.rear = nil
self.front = nil
else
self.front = self.front.next
end
self.size -= 1
end
end
def isSize()
return self.size
end
def isEmpty()
if (self.isSize() == 0)
return true
end
return false
end
def peek()
if (self.isSize() == 0)
return nil
else
return self.front
end
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
def levelAndSum()
if (self.root == nil)
return
end
# Auxiliary variables
sum = 0
level = 0
current = -1
auxiliary = 0
q = MyQueue.new()
# Add first value of queue
q.enqueue(self.root, level)
while (!q.isEmpty())
node = q.peek()
# Remove queue element
q.dequeue()
if (node.level != current)
print("\n")
# Change current level
current = node.level
# Add previous level result
sum += auxiliary
# Get first node of current level
auxiliary = node.n.data
else
# Perform And operation
auxiliary = auxiliary & node.n.data
end
# Display the level node
print(" ", node.n.data)
if (node.n.left != nil)
# Add left node
q.enqueue(node.n.left, node.level + 1)
end
if (node.n.right != nil)
# Add right node
q.enqueue(node.n.right, node.level + 1)
end
end
# Add last level result
sum += auxiliary
print("\n Result : ", sum, "\n")
end
end
def main()
tree1 = BinaryTree.new()
tree2 = BinaryTree.new()
# 1
# / \
# 2 7
# / \ \
# 11 7 19
# /
# -2
# -----------------
# Construct Tree 1
tree1.root = TreeNode.new(1)
tree1.root.left = TreeNode.new(2)
tree1.root.right = TreeNode.new(7)
tree1.root.right.right = TreeNode.new(19)
tree1.root.left.right = TreeNode.new(7)
tree1.root.left.left = TreeNode.new(11)
tree1.root.right.right.left = TreeNode.new(-2)
# 3
# / \
# 2 7
# / \
# 7 8
# -----------------
# Construct Tree 2
tree2.root = TreeNode.new(3)
tree2.root.left = TreeNode.new(2)
tree2.root.right = TreeNode.new(7)
tree2.root.left.right = TreeNode.new(8)
tree2.root.left.left = TreeNode.new(7)
# 1
# / \
# 2 7
# / \ \
# 11 7 19
# /
# -2
# -----------------
# Tree 1
# -----------------
# 1 1 = 1
# / \
# 2 7 2 & 7 = 2
# / \ \
# 11 7 19 11 & 7 & 19 = 3
# /
# -2 -2 = -2
# -----------------------------------------
# 1 + 2 + 3 -2 = 4
tree1.levelAndSum()
# 3
# / \
# 2 7
# / \
# 7 8
# -----------------
# Tree 2
# ----------------
# 3 3 = 3
# / \
# 2 7 2 & 7 = 2
# / \
# 7 8 7 & 8 = 0
# -----------------------------------------
# 3 + 2 + 0 = 5
tree2.levelAndSum()
end
main()
Output
1
2 7
11 7 19
-2
Result : 4
3
2 7
7 8
Result : 5
/*
Scala program for
Level sum of bitwise and operation in binary tree
*/
// Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data,null,null);
}
}
// Queue Node
class QNode(var n: TreeNode,
var next: QNode,
var level: Int)
{
def this(n: TreeNode, level: Int)
{
this(n, null,level);
}
}
// Define custom queue class
class MyQueue(var front: QNode,
var rear: QNode,
var size: Int)
{
def this()
{
this(null,null,0);
}
// Add a new node at last of queue
def enqueue(n: TreeNode, level: Int): Unit = {
var node: QNode = new QNode(n, level);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size += 1;
this.rear = node;
}
// Delete front node of queue
def dequeue(): Unit = {
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size -= 1;
}
}
def isSize(): Int = {
return this.size;
}
def isEmpty(): Boolean = {
if (this.isSize() == 0)
{
return true;
}
return false;
}
def peek(): QNode = {
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front;
}
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def levelAndSum(): Unit = {
if (this.root == null)
{
return;
}
// Auxiliary variables
var sum: Int = 0;
var level: Int = 0;
var current: Int = -1;
var auxiliary: Int = 0;
var q: MyQueue = new MyQueue();
// Add first value of queue
q.enqueue(this.root, level);
while (!q.isEmpty())
{
var node: QNode = q.peek();
// Remove queue element
q.dequeue();
if (node.level != current)
{
print("\n");
// Change current level
current = node.level;
// Add previous level result
sum += auxiliary;
// Get first node of current level
auxiliary = node.n.data;
}
else
{
// Perform And operation
auxiliary = auxiliary & node.n.data;
}
// Display the level node
print(" " + node.n.data);
if (node.n.left != null)
{
// Add left node
q.enqueue(node.n.left, node.level + 1);
}
if (node.n.right != null)
{
// Add right node
q.enqueue(node.n.right, node.level + 1);
}
}
// Add last level result
sum += auxiliary;
println("\n Result : " + sum);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree1: BinaryTree = new BinaryTree();
var tree2: BinaryTree = new BinaryTree();
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Construct Tree 1
*/
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(19);
tree1.root.left.right = new TreeNode(7);
tree1.root.left.left = new TreeNode(11);
tree1.root.right.right.left = new TreeNode(-2);
/*
3
/ \
2 7
/ \
7 8
-----------------
Construct Tree 2
*/
tree2.root = new TreeNode(3);
tree2.root.left = new TreeNode(2);
tree2.root.right = new TreeNode(7);
tree2.root.left.right = new TreeNode(8);
tree2.root.left.left = new TreeNode(7);
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Tree 1
-----------------
1 1 = 1
/ \
2 7 2 & 7 = 2
/ \ \
11 7 19 11 & 7 & 19 = 3
/
-2 -2 = -2
-----------------------------------------
1 + 2 + 3 -2 = 4
*/
tree1.levelAndSum();
/*
3
/ \
2 7
/ \
7 8
-----------------
Tree 2
----------------
3 3 = 3
/ \
2 7 2 & 7 = 2
/ \
7 8 7 & 8 = 0
-----------------------------------------
3 + 2 + 0 = 5
*/
tree2.levelAndSum();
}
}
Output
1
2 7
11 7 19
-2
Result : 4
3
2 7
7 8
Result : 5
/*
Swift 4 program for
Level sum of bitwise and operation in 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 QNode
{
var n: TreeNode? ;
var next: QNode? ;
var level: Int;
init(_ n: TreeNode? , _ level : Int)
{
self.n = n;
self.next = nil;
self.level = level;
}
}
// Define custom queue class
class MyQueue
{
var front: QNode? ;
var rear: QNode? ;
var size: Int;
init()
{
self.front = nil;
self.rear = nil;
self.size = 0;
}
// Add a new node at last of queue
func enqueue(_ n: TreeNode? , _ level : Int)
{
let node: QNode = QNode(n, level);
if (self.front == nil)
{
// When first node of queue
self.front = node;
}
else
{
// Add node at last level
self.rear!.next = node;
}
self.size += 1;
self.rear = node;
}
// Delete front node of queue
func dequeue()
{
if (self.front != nil)
{
if (self.rear === self.front)
{
self.rear = nil;
self.front = nil;
}
else
{
self.front = self.front!.next;
}
self.size -= 1;
}
}
func isSize() -> Int
{
return self.size;
}
func isEmpty() -> Bool
{
if (self.isSize() == 0)
{
return true;
}
return false;
}
func peek() -> QNode?
{
if (self.isSize() == 0)
{
return nil;
}
else
{
return self.front;
}
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func levelAndSum()
{
if (self.root == nil)
{
return;
}
// Auxiliary variables
var sum: Int = 0;
let level: Int = 0;
var current: Int = -1;
var auxiliary: Int = 0;
let q: MyQueue = MyQueue();
// Add first value of queue
q.enqueue(self.root, level);
while (!q.isEmpty())
{
let node: QNode = q.peek()!;
// Remove queue element
q.dequeue();
if (node.level != current)
{
print(terminator: "\n");
// Change current level
current = node.level;
// Add previous level result
sum += auxiliary;
// Get first node of current level
auxiliary = node.n!.data;
}
else
{
// Perform And operation
auxiliary = auxiliary & node.n!.data;
}
// Display the level node
print(" ", node.n!.data, terminator: "");
if (node.n!.left != nil)
{
// Add left node
q.enqueue(node.n!.left, node.level + 1);
}
if (node.n!.right != nil)
{
// Add right node
q.enqueue(node.n!.right, node.level + 1);
}
}
// Add last level result
sum += auxiliary;
print("\n Result : ", sum);
}
}
func main()
{
let tree1: BinaryTree = BinaryTree();
let tree2: BinaryTree = BinaryTree();
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Construct Tree 1
*/
tree1.root = TreeNode(1);
tree1.root!.left = TreeNode(2);
tree1.root!.right = TreeNode(7);
tree1.root!.right!.right = TreeNode(19);
tree1.root!.left!.right = TreeNode(7);
tree1.root!.left!.left = TreeNode(11);
tree1.root!.right!.right!.left = TreeNode(-2);
/*
3
/ \
2 7
/ \
7 8
-----------------
Construct Tree 2
*/
tree2.root = TreeNode(3);
tree2.root!.left = TreeNode(2);
tree2.root!.right = TreeNode(7);
tree2.root!.left!.right = TreeNode(8);
tree2.root!.left!.left = TreeNode(7);
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Tree 1
-----------------
1 1 = 1
/ \
2 7 2 & 7 = 2
/ \ \
11 7 19 11 & 7 & 19 = 3
/
-2 -2 = -2
-----------------------------------------
1 + 2 + 3 -2 = 4
*/
tree1.levelAndSum();
/*
3
/ \
2 7
/ \
7 8
-----------------
Tree 2
----------------
3 3 = 3
/ \
2 7 2 & 7 = 2
/ \
7 8 7 & 8 = 0
-----------------------------------------
3 + 2 + 0 = 5
*/
tree2.levelAndSum();
}
main();
Output
1
2 7
11 7 19
-2
Result : 4
3
2 7
7 8
Result : 5
/*
Kotlin program for
Level sum of bitwise and operation in binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QNode
{
var n: TreeNode ? ;
var next: QNode ? ;
var level: Int;
constructor(n: TreeNode ? , level : Int)
{
this.n = n;
this.next = null;
this.level = level;
}
}
// Define custom queue class
class MyQueue
{
var front: QNode ? ;
var rear: QNode ? ;
var size: Int;
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
fun enqueue(n: TreeNode ? , level : Int): Unit
{
val node: QNode = QNode(n, level);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear?.next = node;
}
this.size += 1;
this.rear = node;
}
// Delete front node of queue
fun dequeue(): Unit
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front?.next;
}
this.size -= 1;
}
}
fun isSize(): Int
{
return this.size;
}
fun isEmpty(): Boolean
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
fun peek(): QNode ?
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front;
}
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun levelAndSum(): Unit
{
if (this.root == null)
{
return;
}
// Auxiliary variables
var sum: Int = 0;
val level: Int = 0;
var current: Int = -1;
var auxiliary: Int = 0;
val q: MyQueue = MyQueue();
// Add first value of queue
q.enqueue(this.root, level);
while (!q.isEmpty())
{
val node: QNode = q.peek()!!;
// Remove queue element
q.dequeue();
if (node.level != current)
{
print("\n");
// Change current level
current = node.level;
// Add previous level result
sum += auxiliary;
// Get first node of current level
auxiliary = node.n!!.data;
}
else
{
// Perform And operation
auxiliary = auxiliary and node.n!!.data;
}
// Display the level node
print(" " + node.n!!.data);
if (node.n?.left != null)
{
// Add left node
q.enqueue(node.n!!.left, node.level + 1);
}
if (node.n?.right != null)
{
// Add right node
q.enqueue(node.n!!.right, node.level + 1);
}
}
// Add last level result
sum += auxiliary;
println("\n Result : " + sum);
}
}
fun main(args: Array < String > ): Unit
{
val tree1: BinaryTree = BinaryTree();
val tree2: BinaryTree = BinaryTree();
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Construct Tree 1
*/
tree1.root = TreeNode(1);
tree1.root?.left = TreeNode(2);
tree1.root?.right = TreeNode(7);
tree1.root?.right?.right = TreeNode(19);
tree1.root?.left?.right = TreeNode(7);
tree1.root?.left?.left = TreeNode(11);
tree1.root?.right?.right?.left = TreeNode(-2);
/*
3
/ \
2 7
/ \
7 8
-----------------
Construct Tree 2
*/
tree2.root = TreeNode(3);
tree2.root?.left = TreeNode(2);
tree2.root?.right = TreeNode(7);
tree2.root?.left?.right = TreeNode(8);
tree2.root?.left?.left = TreeNode(7);
/*
1
/ \
2 7
/ \ \
11 7 19
/
-2
-----------------
Tree 1
-----------------
1 1 = 1
/ \
2 7 2 & 7 = 2
/ \ \
11 7 19 11 & 7 & 19 = 3
/
-2 -2 = -2
-----------------------------------------
1 + 2 + 3 -2 = 4
*/
tree1.levelAndSum();
/*
3
/ \
2 7
/ \
7 8
-----------------
Tree 2
----------------
3 3 = 3
/ \
2 7 2 & 7 = 2
/ \
7 8 7 & 8 = 0
-----------------------------------------
3 + 2 + 0 = 5
*/
tree2.levelAndSum();
}
Output
1
2 7
11 7 19
-2
Result : 4
3
2 7
7 8
Result : 5
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