Efficiently find level sum of bitwise and Operation in binary tree
Here given code implementation process.
import java.util.HashMap;
import java.util.ArrayList;
/*
Java program for
Efficiently find 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;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
public void getLevelNodes(
TreeNode node,
HashMap < Integer, ArrayList < Integer >> record,
int level)
{
if (node != null)
{
if (!record.containsKey(level))
{
// Create new level
record.put(level, new ArrayList < Integer > ());
}
// Add level node
record.get(level).add(node.data);
// Visit left and right subtree
getLevelNodes(node.left, record, level + 1);
getLevelNodes(node.right, record, level + 1);
}
}
public void levelAndSum()
{
if (this.root == null)
{
return;
}
// Auxiliary variables
int sum = 0;
int auxiliary = 0;
// Level start 0
int level = 0;
// This are capable to collect level nodes
HashMap < Integer, ArrayList < Integer >> record =
new HashMap < Integer, ArrayList < Integer >> ();
// This are collecting level nodes in binary tree
this.getLevelNodes(this.root, record, 0);
// Execute loop from top to bottom manner level 0 to n
while (level < record.size())
{
ArrayList < Integer > value = record.get(level);
// Execute level nodes
for (int j = 0; j < value.size(); ++j)
{
if (j == 0)
{
auxiliary = value.get(j);
}
else
{
// Perform bitwise And operation
auxiliary = auxiliary & value.get(j);
}
// Display level node
System.out.print(" " + value.get(j));
}
// Include new line
System.out.print("\n");
// Add calculated result
sum += auxiliary;
level++;
}
System.out.println(" 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);
/*
-----------------
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();
/*
-----------------
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>
#include <unordered_map>
#include <vector>
using namespace std;
/*
C++ program for
Efficiently find 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;
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
void getLevelNodes(TreeNode *node,
unordered_map < int, vector < int > > &record,
int level)
{
if (node != NULL)
{
// Add level node
record[level].push_back(node->data);
// Visit left and right subtree
this->getLevelNodes(node->left, record, level + 1);
this->getLevelNodes(node->right, record, level + 1);
}
}
void levelAndSum()
{
if (this->root == NULL)
{
return;
}
// Auxiliary variables
int sum = 0;
int auxiliary = 0;
// Level start 0
int level = 0;
// This are capable to collect level nodes
unordered_map < int, vector < int > > record;
// This are collecting level nodes in binary tree
this->getLevelNodes(this->root, record, 0);
// Execute loop from top to bottom manner level 0 to n
while (level < record.size())
{
// Execute level nodes
for (int j = 0; j < record[level].size(); ++j)
{
if (j == 0)
{
auxiliary = record[level][j];
}
else
{
// Perform bitwise And operation
auxiliary = auxiliary & record[level][j];
}
// Display level node
cout << " " << record[level][j];
}
// Include new line
cout << "\n";
// Add calculated result
sum += auxiliary;
level++;
}
cout << " 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);
/*
-----------------
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();
/*
-----------------
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;
using System.Collections.Generic;
/*
Csharp program for
Efficiently find 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;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
public void getLevelNodes(TreeNode node,
Dictionary < int, List < int >> record,
int level)
{
if (node != null)
{
if (!record.ContainsKey(level))
{
// Create new level
record.Add(level, new List < int > ());
}
// Add level node
record[level].Add(node.data);
// Visit left and right subtree
this.getLevelNodes(node.left, record, level + 1);
this.getLevelNodes(node.right, record, level + 1);
}
}
public void levelAndSum()
{
if (this.root == null)
{
return;
}
// Auxiliary variables
int sum = 0;
int auxiliary = 0;
// Level start 0
int level = 0;
// This are capable to collect level nodes
Dictionary < int, List < int >> record =
new Dictionary < int, List < int >> ();
// This are collecting level nodes in binary tree
this.getLevelNodes(this.root, record, 0);
// Execute loop from top to bottom manner level 0 to n
while (level < record.Count)
{
List < int > value = record[level];
// Execute level nodes
for (int j = 0; j < value.Count; ++j)
{
if (j == 0)
{
auxiliary = value[j];
}
else
{
// Perform bitwise And operation
auxiliary = auxiliary & value[j];
}
// Display level node
Console.Write(" " + value[j]);
}
// Include new line
Console.Write("\n");
// Add calculated result
sum += auxiliary;
level++;
}
Console.WriteLine(" 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);
/*
-----------------
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();
/*
-----------------
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 : 5package main
import "fmt"
/*
Go program for
Efficiently find 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
}
type BinaryTree struct {
root * TreeNode
}
func getBinaryTree() * BinaryTree {
var me *BinaryTree = &BinaryTree {}
// Set initial value
me.root = nil
return me
}
func(this *BinaryTree) getLevelNodes(node * TreeNode,
record map[int] [] int,
level int) {
if node != nil {
if _, found := record[level] ; !found {
// Create new level
record[level] = make([]int,0)
}
// Add level node
record[level] = append(record[level], node.data)
// Visit left and right subtree
this.getLevelNodes(node.left, record, level + 1)
this.getLevelNodes(node.right, record, level + 1)
}
}
func(this BinaryTree) levelAndSum() {
if this.root == nil {
return
}
// Auxiliary variables
var sum int = 0
var auxiliary int = 0
// Level start 0
var level int = 0
// This are capable to collect level nodes
var record = make(map[int] [] int )
// This are collecting level nodes in binary tree
this.getLevelNodes(this.root, record, 0)
// Execute loop from top to bottom manner level 0 to n
for (level < len(record)) {
var value = record[level]
// Execute level nodes
for j := 0 ; j < len(value) ; j++ {
if j == 0 {
auxiliary = value[j]
} else {
// Perform bitwise And operation
auxiliary = auxiliary & value[j]
}
// Display level node
fmt.Print(" ", value[j])
}
// Include new line
fmt.Print("\n")
// Add calculated result
sum += auxiliary
level++
}
fmt.Println(" 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)
/*
-----------------
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()
/*
-----------------
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
Efficiently find 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;
}
}
class BinaryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
public function getLevelNodes($node, &$record, $level)
{
if ($node != NULL)
{
if (!array_key_exists($level, $record))
{
// Create new level
$record[$level] = array();
}
// Add level node
$record[$level][] = $node->data;
// Visit left and right subtree
$this->getLevelNodes($node->left, $record, $level + 1);
$this->getLevelNodes($node->right, $record, $level + 1);
}
}
public function levelAndSum()
{
if ($this->root == NULL)
{
return;
}
// Auxiliary variables
$sum = 0;
$auxiliary = 0;
// Level start 0
$level = 0;
// This are capable to collect level nodes
$record = array();
// This are collecting level nodes in binary tree
$this->getLevelNodes($this->root, $record, 0);
// Execute loop from top to bottom manner level 0 to n
while ($level < count($record))
{
$value = $record[$level];
// Execute level nodes
for ($j = 0; $j < count($value); ++$j)
{
if ($j == 0)
{
$auxiliary = $value[$j];
}
else
{
// Perform bitwise And operation
$auxiliary = $auxiliary & $value[$j];
}
// Display level node
echo(" ".$value[$j]);
}
// Include new line
echo("\n");
// Add calculated result
$sum += $auxiliary;
$level++;
}
echo(" 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);
/*
-----------------
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();
/*
-----------------
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
Efficiently find 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;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
getLevelNodes(node, record, level)
{
if (node != null)
{
if (!record.has(level))
{
// Create new level
record.set(level, []);
}
// Add level node
record.get(level).push(node.data);
// Visit left and right subtree
this.getLevelNodes(node.left, record, level + 1);
this.getLevelNodes(node.right, record, level + 1);
}
}
levelAndSum()
{
if (this.root == null)
{
return;
}
// Auxiliary variables
var sum = 0;
var auxiliary = 0;
// Level start 0
var level = 0;
// This are capable to collect level nodes
var record = new Map();
// This are collecting level nodes in binary tree
this.getLevelNodes(this.root, record, 0);
// Execute loop from top to bottom manner level 0 to n
while (level < record.size)
{
var value = record.get(level);
// Execute level nodes
for (var j = 0; j < value.length; ++j)
{
if (j == 0)
{
auxiliary = value[j];
}
else
{
// Perform bitwise And operation
auxiliary = auxiliary & value[j];
}
// Display level node
process.stdout.write(" " + value[j]);
}
// Include new line
process.stdout.write("\n");
// Add calculated result
sum += auxiliary;
level++;
}
console.log(" 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);
/*
-----------------
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();
/*
-----------------
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
# Efficiently find 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
class BinaryTree :
def __init__(self) :
self.root = None
def getLevelNodes(self, node, record, level) :
if (node != None) :
if (not(level in record.keys())) :
# Create new level
record[level] = []
# Add level node
record.get(level).append(node.data)
# Visit left and right subtree
self.getLevelNodes(node.left, record, level + 1)
self.getLevelNodes(node.right, record, level + 1)
def levelAndSum(self) :
if (self.root == None) :
return
# Auxiliary variables
sum = 0
auxiliary = 0
# Level start 0
level = 0
# This are capable to collect level nodes
record = dict()
# This are collecting level nodes in binary tree
self.getLevelNodes(self.root, record, 0)
# Execute loop from top to bottom manner level 0 to n
while (level < len(record)) :
value = record.get(level)
j = 0
# Execute level nodes
while (j < len(value)) :
if (j == 0) :
auxiliary = value[j]
else :
# Perform bitwise And operation
auxiliary = auxiliary & value[j]
# Display level node
print(" ", value[j], end = "")
j += 1
# Include new line
print(end = "\n")
# Add calculated result
sum += auxiliary
level += 1
print(" 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)
# -----------------
# 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()
# -----------------
# 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
# Efficiently find 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
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
def getLevelNodes(node, record, level)
if (node != nil)
if (!record.key?(level))
# Create new level
record[level] = []
end
# Add level node
record[level].push(node.data)
# Visit left and right subtree
self.getLevelNodes(node.left, record, level + 1)
self.getLevelNodes(node.right, record, level + 1)
end
end
def levelAndSum()
if (self.root == nil)
return
end
# Auxiliary variables
sum = 0
auxiliary = 0
# Level start 0
level = 0
# This are capable to collect level nodes
record = Hash.new()
# This are collecting level nodes in binary tree
self.getLevelNodes(self.root, record, 0)
# Execute loop from top to bottom manner level 0 to n
while (level < record.size())
value = record[level]
j = 0
# Execute level nodes
while (j < value.length)
if (j == 0)
auxiliary = value[j]
else
# Perform bitwise And operation
auxiliary = auxiliary & value[j]
end
# Display level node
print(" ", value[j])
j += 1
end
# Include new line
print("\n")
# Add calculated result
sum += auxiliary
level += 1
end
print(" 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)
# -----------------
# 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()
# -----------------
# 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
import scala.collection.mutable._;
/*
Scala program for
Efficiently find 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);
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def getLevelNodes(
node: TreeNode,
record: HashMap[Int, ArrayBuffer[Int]],
level: Int): Unit = {
if (node != null)
{
if (!record.contains(level))
{
// Create new level
record.addOne(level, new ArrayBuffer[Int]());
}
// Add level node
record.get(level).get += node.data;
// Visit left and right subtree
getLevelNodes(node.left, record, level + 1);
getLevelNodes(node.right, record, level + 1);
}
}
def levelAndSum(): Unit = {
if (this.root == null)
{
return;
}
// Auxiliary variables
var sum: Int = 0;
var auxiliary: Int = 0;
// Level start 0
var level: Int = 0;
// This are capable to collect level nodes
var record: HashMap[Int, ArrayBuffer[Int]] =
new HashMap[Int, ArrayBuffer[Int]]();
// This are collecting level nodes in binary tree
this.getLevelNodes(this.root, record, 0);
// Execute loop from top to bottom manner level 0 to n
while (level < record.size)
{
var value: ArrayBuffer[Int] = record.get(level).get;
var j: Int = 0;
// Execute level nodes
while (j < value.size)
{
if (j == 0)
{
auxiliary = value(j);
}
else
{
// Perform bitwise And operation
auxiliary = auxiliary & value(j);
}
// Display level node
print(" " + value(j));
j += 1;
}
// Include new line
print("\n");
// Add calculated result
sum += auxiliary;
level += 1;
}
println(" 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);
/*
-----------------
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();
/*
-----------------
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 : 5import Foundation;
/*
Swift 4 program for
Efficiently find 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;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func getLevelNodes(_ node: TreeNode? ,
_ record : inout[Int : [Int] ],
_ level: Int)
{
if (node != nil)
{
if (!record.keys.contains(level))
{
// Create new level
record[level] = [Int]();
}
// Add level node
record[level]!.append(node!.data);
// Visit left and right subtree
self.getLevelNodes(node!.left, &record, level + 1);
self.getLevelNodes(node!.right, &record, level + 1);
}
}
func levelAndSum()
{
if (self.root == nil)
{
return;
}
// Auxiliary variables
var sum: Int = 0;
var auxiliary: Int = 0;
// Level start 0
var level: Int = 0;
// This are capable to collect level nodes
var record: [Int : [Int]] = [Int : [Int]]();
// This are collecting level nodes in binary tree
self.getLevelNodes(self.root, &record, 0);
// Execute loop from top to bottom manner level 0 to n
while (level < record.count)
{
let value: [Int] = record[level]!;
var j: Int = 0;
// Execute level nodes
while (j < value.count)
{
if (j == 0)
{
auxiliary = value[j];
}
else
{
// Perform bitwise And operation
auxiliary = auxiliary & value[j];
}
// Display level node
print(" ", value[j], terminator: "");
j += 1;
}
// Include new line
print(terminator: "\n");
// Add calculated result
sum += auxiliary;
level += 1;
}
print(" 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);
/*
-----------------
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();
/*
-----------------
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
Efficiently find 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;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun getLevelNodes(
node: TreeNode ? ,
record : HashMap < Int, MutableList < Int >> ,
level : Int): Unit
{
if (node != null)
{
if (!record.containsKey(level))
{
// Create new level
record.put(level, mutableListOf < Int > ());
}
// Add level node
record.getValue(level).add(node.data);
// Visit left and right subtree
this.getLevelNodes(node.left, record, level + 1);
this.getLevelNodes(node.right, record, level + 1);
}
}
fun levelAndSum(): Unit
{
if (this.root == null)
{
return;
}
// Auxiliary variables
var sum: Int = 0;
var auxiliary: Int = 0;
// Level start 0
var level: Int = 0;
// This are capable to collect level nodes
val record = HashMap < Int,MutableList< Int >> ();
// This are collecting level nodes in binary tree
this.getLevelNodes(this.root, record, 0);
// Execute loop from top to bottom manner level 0 to n
while (level < record.count())
{
val value: MutableList < Int > = record.getValue(level);
var j: Int = 0;
// Execute level nodes
while (j < value.size)
{
if (j == 0)
{
auxiliary = value[j];
}
else
{
// Perform bitwise And operation
auxiliary = auxiliary and value[j];
}
// Display level node
print(" " + value[j]);
j += 1;
}
// Include new line
print("\n");
// Add calculated result
sum += auxiliary;
level += 1;
}
println(" 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);
/*
-----------------
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();
/*
-----------------
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