Maximum Bitwise AND value in binary tree path from root to leaf nodes
Here given code implementation process.
// C program for
// Maximum Bitwise AND value in binary tree path from root to leaf nodes
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// Tree Node
struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};
// Binary Tree
struct BinaryTree
{
struct TreeNode *root;
};
// Create new tree
struct BinaryTree *newTree()
{
// Create a dynamic tree
struct BinaryTree *tree =
(struct BinaryTree *) malloc(sizeof(struct BinaryTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
//return new tree
return tree;
}
// This is creates and returns the new binary tree node
struct TreeNode *getNode(int data)
{
// Create dynamic node
struct TreeNode *node =
(struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
//Set data and pointer values
node->data = data;
node->left = NULL;
node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return node;
}
// Find maximum Bitwise AND in binary tree path using recursion
void maximumBitwiseAND(struct TreeNode *node, int value, int *result)
{
if (node != NULL)
{
if ((node->left == NULL && node->right == NULL))
{
if ((value & node->data) > *result)
{
// Get new result
*result = value & node->data;
}
}
else if ((value & node->data) <= *result)
{
// Stop recursion When current path Bitwise And
// are less than result
return;
}
else
{
// Visit left subtree
maximumBitwiseAND(node->left, value & node->data, result);
// Visit right subtree
maximumBitwiseAND(node->right, value & node->data, result);
}
}
}
// Handles the request of finding maximum AND in binary Tree path
void pathBitwiseAND(struct TreeNode *node)
{
if (node == NULL)
{
// Empty tree
return;
}
// Set initial minimum value
int result = INT_MIN;
// Find maximum And
maximumBitwiseAND(node, node->data, & result);
// Display calculated result
printf("\n Maximum Bitwise AND : %d", result);
}
int main(int argc, char
const *argv[])
{
struct BinaryTree *tree = newTree();
/*
15
/ \
-4 10
/ \ \
6 12 6
/ / \ /
4 6 8 2
/
9
-----------------
Constructing binary tree
*/
tree->root = getNode(15);
tree->root->left = getNode(-4);
tree->root->left->right = getNode(12);
tree->root->left->right->left = getNode(6);
tree->root->left->right->left->left = getNode(9);
tree->root->left->right->right = getNode(8);
tree->root->left->left = getNode(6);
tree->root->left->left->left = getNode(4);
tree->root->right = getNode(10);
tree->root->right->right = getNode(6);
tree->root->right->right->left = getNode(2);
/*
(15 & -4 & 6 & 4 ) = 4
(15 & -4 & 12 & 6 & 9) = 0
(15 & -4 & 12 & 8) = 8
(15 & 10 & 6 & 2 ) = 2
Result is : 8
*/
pathBitwiseAND(tree->root);
return 0;
}input
Maximum Bitwise AND : 8/*
Java Program
Maximum Bitwise AND value in binary tree
Path from root to leaf nodes
*/
// 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 int result;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
this.result = 0;
}
// Find maximum Bitwise AND in binary tree path using recursion
public void maximumBitwiseAND(TreeNode node, int value)
{
if (node != null)
{
if ((node.left == null && node.right == null))
{
if ((value & node.data) > this.result)
{
// Get new result
this.result = value & node.data;
}
}
else if ((value & node.data) <= this.result)
{
// Stop recursion When current path Bitwise And
// are less than result
return;
}
else
{
// Visit left subtree
maximumBitwiseAND(node.left, value & node.data);
// Visit right subtree
maximumBitwiseAND(node.right, value & node.data);
}
}
}
// Handles the request of finding maximum AND in binary Tree path
public void pathBitwiseAND()
{
if (this.root == null)
{
// Empty tree
return;
}
// Set initial minimum value
this.result = Integer.MIN_VALUE;
// Find maximum And
maximumBitwiseAND(this.root, this.root.data);
// Display calculated result
System.out.print("\n Maximum Bitwise AND : " + this.result);
}
public static void main(String[] args)
{
// Create new binary trees
BinaryTree tree = new BinaryTree();
/*
15
/ \
-4 10
/ \ \
6 12 6
/ / \ /
4 6 8 2
/
9
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(15);
tree.root.left = new TreeNode(-4);
tree.root.left.right = new TreeNode(12);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.left = new TreeNode(6);
tree.root.left.left.left = new TreeNode(4);
tree.root.right = new TreeNode(10);
tree.root.right.right = new TreeNode(6);
tree.root.right.right.left = new TreeNode(2);
/*
(15 & -4 & 6 & 4 ) = 4
(15 & -4 & 12 & 6 & 9) = 0
(15 & -4 & 12 & 8) = 8
(15 & 10 & 6 & 2 ) = 2
Result is : 8
*/
tree.pathBitwiseAND();
}
}input
Maximum Bitwise AND : 8// Include header file
#include <iostream>
#include <limits.h>
using namespace std;
/*
C++ Program
Maximum Bitwise AND value in binary tree
Path from root to leaf nodes
*/
// 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;
int result;
BinaryTree()
{
this->root = NULL;
this->result = 0;
}
// Find maximum Bitwise AND in binary tree path using recursion
void maximumBitwiseAND(TreeNode *node, int value)
{
if (node != NULL)
{
if ((node->left == NULL && node->right == NULL))
{
if ((value &node->data) > this->result)
{
// Get new result
this->result = value &node->data;
}
}
else if ((value &node->data) <= this->result)
{
// Stop recursion When current path Bitwise And
// are less than result
return;
}
else
{
// Visit left subtree
this->maximumBitwiseAND(node->left, value &node->data);
// Visit right subtree
this->maximumBitwiseAND(node->right, value &node->data);
}
}
}
// Handles the request of finding maximum AND in binary Tree path
void pathBitwiseAND()
{
if (this->root == NULL)
{
// Empty tree
return;
}
// Set initial minimum value
this->result = INT_MIN;
// Find maximum And
this->maximumBitwiseAND(this->root, this->root->data);
// Display calculated result
cout << "\n Maximum Bitwise AND : " << this->result;
}
};
int main()
{
// Create new binary trees
BinaryTree *tree = new BinaryTree();
/*
15
/ \
-4 10
/ \ \
6 12 6
/ / \ /
4 6 8 2
/
9
-----------------
Constructing binary tree
*/
tree->root = new TreeNode(15);
tree->root->left = new TreeNode(-4);
tree->root->left->right = new TreeNode(12);
tree->root->left->right->left = new TreeNode(6);
tree->root->left->right->left->left = new TreeNode(9);
tree->root->left->right->right = new TreeNode(8);
tree->root->left->left = new TreeNode(6);
tree->root->left->left->left = new TreeNode(4);
tree->root->right = new TreeNode(10);
tree->root->right->right = new TreeNode(6);
tree->root->right->right->left = new TreeNode(2);
/*
(15 &-4 &6 &4 ) = 4
(15 &-4 &12 &6 &9) = 0
(15 &-4 &12 &8) = 8
(15 &10 &6 &2 ) = 2
Result is : 8
*/
tree->pathBitwiseAND();
return 0;
}input
Maximum Bitwise AND : 8// Include namespace system
using System;
/*
Csharp Program
Maximum Bitwise AND value in binary tree
Path from root to leaf nodes
*/
// 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 int result;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
this.result = 0;
}
// Find maximum Bitwise AND in binary tree path using recursion
public void maximumBitwiseAND(TreeNode node, int value)
{
if (node != null)
{
if ((node.left == null && node.right == null))
{
if ((value & node.data) > this.result)
{
// Get new result
this.result = value & node.data;
}
}
else if ((value & node.data) <= this.result)
{
// Stop recursion When current path Bitwise And
// are less than result
return;
}
else
{
// Visit left subtree
this.maximumBitwiseAND(node.left, value & node.data);
// Visit right subtree
this.maximumBitwiseAND(node.right, value & node.data);
}
}
}
// Handles the request of finding maximum AND in binary Tree path
public void pathBitwiseAND()
{
if (this.root == null)
{
// Empty tree
return;
}
// Set initial minimum value
this.result = int.MinValue;
// Find maximum And
this.maximumBitwiseAND(this.root, this.root.data);
// Display calculated result
Console.Write("\n Maximum Bitwise AND : " + this.result);
}
public static void Main(String[] args)
{
// Create new binary trees
BinaryTree tree = new BinaryTree();
/*
15
/ \
-4 10
/ \ \
6 12 6
/ / \ /
4 6 8 2
/
9
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(15);
tree.root.left = new TreeNode(-4);
tree.root.left.right = new TreeNode(12);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.left = new TreeNode(6);
tree.root.left.left.left = new TreeNode(4);
tree.root.right = new TreeNode(10);
tree.root.right.right = new TreeNode(6);
tree.root.right.right.left = new TreeNode(2);
/*
(15 & -4 & 6 & 4 ) = 4
(15 & -4 & 12 & 6 & 9) = 0
(15 & -4 & 12 & 8) = 8
(15 & 10 & 6 & 2 ) = 2
Result is : 8
*/
tree.pathBitwiseAND();
}
}input
Maximum Bitwise AND : 8<?php
/*
Php Program
Maximum Bitwise AND value in binary tree
Path from root to leaf nodes
*/
// 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 $result;
public function __construct()
{
$this->root = NULL;
$this->result = 0;
}
// Find maximum Bitwise AND in binary tree path using recursion
public function maximumBitwiseAND($node, $value)
{
if ($node != NULL)
{
if (($node->left == NULL && $node->right == NULL))
{
if (($value & $node->data) > $this->result)
{
// Get new result
$this->result = $value & $node->data;
}
}
else if (($value & $node->data) <= $this->result)
{
// Stop recursion When current path Bitwise And
// are less than result
return;
}
else
{
// Visit left subtree
$this->maximumBitwiseAND($node->left, $value & $node->data);
// Visit right subtree
$this->maximumBitwiseAND($node->right, $value & $node->data);
}
}
}
// Handles the request of finding maximum AND in binary Tree path
public function pathBitwiseAND()
{
if ($this->root == NULL)
{
// Empty tree
return;
}
// Set initial minimum value
$this->result = -PHP_INT_MAX;
// Find maximum And
$this->maximumBitwiseAND($this->root, $this->root->data);
// Display calculated result
echo("\n Maximum Bitwise AND : ".$this->result);
}
}
function main()
{
// Create new binary trees
$tree = new BinaryTree();
/*
15
/ \
-4 10
/ \ \
6 12 6
/ / \ /
4 6 8 2
/
9
-----------------
Constructing binary tree
*/
$tree->root = new TreeNode(15);
$tree->root->left = new TreeNode(-4);
$tree->root->left->right = new TreeNode(12);
$tree->root->left->right->left = new TreeNode(6);
$tree->root->left->right->left->left = new TreeNode(9);
$tree->root->left->right->right = new TreeNode(8);
$tree->root->left->left = new TreeNode(6);
$tree->root->left->left->left = new TreeNode(4);
$tree->root->right = new TreeNode(10);
$tree->root->right->right = new TreeNode(6);
$tree->root->right->right->left = new TreeNode(2);
/*
(15 & -4 & 6 & 4 ) = 4
(15 & -4 & 12 & 6 & 9) = 0
(15 & -4 & 12 & 8) = 8
(15 & 10 & 6 & 2 ) = 2
Result is : 8
*/
$tree->pathBitwiseAND();
}
main();input
Maximum Bitwise AND : 8/*
Node JS Program
Maximum Bitwise AND value in binary tree
Path from root to leaf nodes
*/
// 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;
this.result = 0;
}
// Find maximum Bitwise AND in binary tree path using recursion
maximumBitwiseAND(node, value)
{
if (node != null)
{
if ((node.left == null && node.right == null))
{
if ((value & node.data) > this.result)
{
// Get new result
this.result = value & node.data;
}
}
else if ((value & node.data) <= this.result)
{
// Stop recursion When current path Bitwise And
// are less than result
return;
}
else
{
// Visit left subtree
this.maximumBitwiseAND(node.left, value & node.data);
// Visit right subtree
this.maximumBitwiseAND(node.right, value & node.data);
}
}
}
// Handles the request of finding maximum AND in binary Tree path
pathBitwiseAND()
{
if (this.root == null)
{
// Empty tree
return;
}
// Set initial minimum value
this.result = -Number.MAX_VALUE;
// Find maximum And
this.maximumBitwiseAND(this.root, this.root.data);
// Display calculated result
process.stdout.write("\n Maximum Bitwise AND : " + this.result);
}
}
function main()
{
// Create new binary trees
var tree = new BinaryTree();
/*
15
/ \
-4 10
/ \ \
6 12 6
/ / \ /
4 6 8 2
/
9
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(15);
tree.root.left = new TreeNode(-4);
tree.root.left.right = new TreeNode(12);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.left = new TreeNode(6);
tree.root.left.left.left = new TreeNode(4);
tree.root.right = new TreeNode(10);
tree.root.right.right = new TreeNode(6);
tree.root.right.right.left = new TreeNode(2);
/*
(15 & -4 & 6 & 4 ) = 4
(15 & -4 & 12 & 6 & 9) = 0
(15 & -4 & 12 & 8) = 8
(15 & 10 & 6 & 2 ) = 2
Result is : 8
*/
tree.pathBitwiseAND();
}
main();input
Maximum Bitwise AND : 8import sys
# Python 3 Program
# Maximum Bitwise AND value in binary tree
# Path from root to leaf nodes
# 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
self.result = 0
# Find maximum Bitwise AND in binary tree path using recursion
def maximumBitwiseAND(self, node, value) :
if (node != None) :
if ((node.left == None and node.right == None)) :
if ((value & node.data) > self.result) :
# Get new result
self.result = value & node.data
elif ((value & node.data) <= self.result) :
# Stop recursion When current path Bitwise And
# are less than result
return
else :
# Visit left subtree
self.maximumBitwiseAND(node.left, value & node.data)
# Visit right subtree
self.maximumBitwiseAND(node.right, value & node.data)
# Handles the request of finding maximum AND in binary Tree path
def pathBitwiseAND(self) :
if (self.root == None) :
# Empty tree
return
# Set initial minimum value
self.result = -sys.maxsize
# Find maximum And
self.maximumBitwiseAND(self.root, self.root.data)
# Display calculated result
print("\n Maximum Bitwise AND : ", self.result, end = "")
def main() :
# Create new binary trees
tree = BinaryTree()
# 15
# / \
# -4 10
# / \ \
# 6 12 6
# / / \ /
# 4 6 8 2
# /
# 9
# -----------------
# Constructing binary tree
tree.root = TreeNode(15)
tree.root.left = TreeNode(-4)
tree.root.left.right = TreeNode(12)
tree.root.left.right.left = TreeNode(6)
tree.root.left.right.left.left = TreeNode(9)
tree.root.left.right.right = TreeNode(8)
tree.root.left.left = TreeNode(6)
tree.root.left.left.left = TreeNode(4)
tree.root.right = TreeNode(10)
tree.root.right.right = TreeNode(6)
tree.root.right.right.left = TreeNode(2)
# (15 & -4 & 6 & 4 ) = 4
# (15 & -4 & 12 & 6 & 9) = 0
# (15 & -4 & 12 & 8) = 8
# (15 & 10 & 6 & 2 ) = 2
# Result is : 8
tree.pathBitwiseAND()
if __name__ == "__main__": main()input
Maximum Bitwise AND : 8# Ruby Program
# Maximum Bitwise AND value in binary tree
# Path from root to leaf nodes
# 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, :result
attr_accessor :root, :result
def initialize()
self.root = nil
self.result = 0
end
# Find maximum Bitwise AND in binary tree path using recursion
def maximumBitwiseAND(node, value)
if (node != nil)
if ((node.left == nil && node.right == nil))
if ((value & node.data) > self.result)
# Get new result
self.result = value & node.data
end
elsif ((value & node.data) <= self.result)
# Stop recursion When current path Bitwise And
# are less than result
return
else
# Visit left subtree
self.maximumBitwiseAND(node.left, value & node.data)
# Visit right subtree
self.maximumBitwiseAND(node.right, value & node.data)
end
end
end
# Handles the request of finding maximum AND in binary Tree path
def pathBitwiseAND()
if (self.root == nil)
# Empty tree
return
end
# Set initial minimum value
self.result = -(2 ** (0. size * 8 - 2))
# Find maximum And
self.maximumBitwiseAND(self.root, self.root.data)
# Display calculated result
print("\n Maximum Bitwise AND : ", self.result)
end
end
def main()
# Create new binary trees
tree = BinaryTree.new()
# 15
# / \
# -4 10
# / \ \
# 6 12 6
# / / \ /
# 4 6 8 2
# /
# 9
# -----------------
# Constructing binary tree
tree.root = TreeNode.new(15)
tree.root.left = TreeNode.new(-4)
tree.root.left.right = TreeNode.new(12)
tree.root.left.right.left = TreeNode.new(6)
tree.root.left.right.left.left = TreeNode.new(9)
tree.root.left.right.right = TreeNode.new(8)
tree.root.left.left = TreeNode.new(6)
tree.root.left.left.left = TreeNode.new(4)
tree.root.right = TreeNode.new(10)
tree.root.right.right = TreeNode.new(6)
tree.root.right.right.left = TreeNode.new(2)
# (15 & -4 & 6 & 4 ) = 4
# (15 & -4 & 12 & 6 & 9) = 0
# (15 & -4 & 12 & 8) = 8
# (15 & 10 & 6 & 2 ) = 2
# Result is : 8
tree.pathBitwiseAND()
end
main()input
Maximum Bitwise AND : 8/*
Scala Program
Maximum Bitwise AND value in binary tree
Path from root to leaf nodes
*/
// 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,
var result: Int)
{
def this()
{
this(null,0);
}
// Find maximum Bitwise AND in binary tree path using recursion
def maximumBitwiseAND(node: TreeNode, value: Int): Unit = {
if (node != null)
{
if ((node.left == null && node.right == null))
{
if ((value & node.data) > this.result)
{
// Get new result
this.result = value & node.data;
}
}
else if ((value & node.data) <= this.result)
{
// Stop recursion When current path Bitwise And
// are less than result
return;
}
else
{
// Visit left subtree
maximumBitwiseAND(node.left, value & node.data);
// Visit right subtree
maximumBitwiseAND(node.right, value & node.data);
}
}
}
// Handles the request of finding maximum AND in binary Tree path
def pathBitwiseAND(): Unit = {
if (this.root == null)
{
// Empty tree
return;
}
// Set initial minimum value
this.result = Int.MinValue;
// Find maximum And
maximumBitwiseAND(this.root, this.root.data);
// Display calculated result
print("\n Maximum Bitwise AND : " + this.result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create new binary trees
var tree: BinaryTree = new BinaryTree();
/*
15
/ \
-4 10
/ \ \
6 12 6
/ / \ /
4 6 8 2
/
9
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(15);
tree.root.left = new TreeNode(-4);
tree.root.left.right = new TreeNode(12);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.left = new TreeNode(6);
tree.root.left.left.left = new TreeNode(4);
tree.root.right = new TreeNode(10);
tree.root.right.right = new TreeNode(6);
tree.root.right.right.left = new TreeNode(2);
/*
(15 & -4 & 6 & 4 ) = 4
(15 & -4 & 12 & 6 & 9) = 0
(15 & -4 & 12 & 8) = 8
(15 & 10 & 6 & 2 ) = 2
Result is : 8
*/
tree.pathBitwiseAND();
}
}input
Maximum Bitwise AND : 8/*
Swift 4 Program
Maximum Bitwise AND value in binary tree
Path from root to leaf nodes
*/
// 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? ;
var result: Int;
init()
{
self.root = nil;
self.result = 0;
}
// Find maximum Bitwise AND in binary tree path using recursion
func maximumBitwiseAND(_ node: TreeNode? , _ value : Int)
{
if (node != nil)
{
if ((node!.left == nil && node!.right == nil))
{
if ((value & node!.data) > self.result)
{
// Get new result
self.result = value & node!.data;
}
}
else if ((value & node!.data) <= self.result)
{
// Stop recursion When current path Bitwise And
// are less than result
return;
}
else
{
// Visit left subtree
self.maximumBitwiseAND(node!.left, value & node!.data);
// Visit right subtree
self.maximumBitwiseAND(node!.right, value & node!.data);
}
}
}
// Handles the request of finding maximum AND in binary Tree path
func pathBitwiseAND()
{
if (self.root == nil)
{
// Empty tree
return;
}
// Set initial minimum value
self.result = Int.min;
// Find maximum And
self.maximumBitwiseAND(self.root, self.root!.data);
// Display calculated result
print("\n Maximum Bitwise AND : ", self.result, terminator: "");
}
}
func main()
{
// Create new binary trees
let tree = BinaryTree();
/*
15
/ \
-4 10
/ \ \
6 12 6
/ / \ /
4 6 8 2
/
9
-----------------
Constructing binary tree
*/
tree.root = TreeNode(15);
tree.root!.left = TreeNode(-4);
tree.root!.left!.right = TreeNode(12);
tree.root!.left!.right!.left = TreeNode(6);
tree.root!.left!.right!.left!.left = TreeNode(9);
tree.root!.left!.right!.right = TreeNode(8);
tree.root!.left!.left = TreeNode(6);
tree.root!.left!.left!.left = TreeNode(4);
tree.root!.right = TreeNode(10);
tree.root!.right!.right = TreeNode(6);
tree.root!.right!.right!.left = TreeNode(2);
/*
(15 & -4 & 6 & 4 ) = 4
(15 & -4 & 12 & 6 & 9) = 0
(15 & -4 & 12 & 8) = 8
(15 & 10 & 6 & 2 ) = 2
Result is : 8
*/
tree.pathBitwiseAND();
}
main();input
Maximum Bitwise AND : 8/*
Kotlin Program
Maximum Bitwise AND value in binary tree
Path from root to leaf nodes
*/
// 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 ? ;
var result: Int;
constructor()
{
this.root = null;
this.result = 0;
}
// Find maximum Bitwise AND in binary tree path using recursion
fun maximumBitwiseAND(node: TreeNode ? , value : Int): Unit
{
if (node != null)
{
if ((node.left == null && node.right == null))
{
if ((value and node.data) > this.result)
{
// Get new result
this.result = value and node.data;
}
}
else if ((value and node.data) <= this.result)
{
// Stop recursion When current path Bitwise And
// are less than result
return;
}
else
{
// Visit left subtree
this.maximumBitwiseAND(node.left, value and node.data);
// Visit right subtree
this.maximumBitwiseAND(node.right, value and node.data);
}
}
}
// Handles the request of finding maximum AND in binary Tree path
fun pathBitwiseAND(): Unit
{
if (this.root == null)
{
// Empty tree
return;
}
// Set initial minimum value
this.result = Int.MIN_VALUE;
// Find maximum And
this.maximumBitwiseAND(this.root, this.root!!.data);
// Display calculated result
print("\n Maximum Bitwise AND : " + this.result);
}
}
fun main(args: Array < String > ): Unit
{
// Create new binary trees
val tree: BinaryTree = BinaryTree();
/*
15
/ \
-4 10
/ \ \
6 12 6
/ / \ /
4 6 8 2
/
9
-----------------
Constructing binary tree
*/
tree.root = TreeNode(15);
tree.root?.left = TreeNode(-4);
tree.root?.left?.right = TreeNode(12);
tree.root?.left?.right?.left = TreeNode(6);
tree.root?.left?.right?.left?.left = TreeNode(9);
tree.root?.left?.right?.right = TreeNode(8);
tree.root?.left?.left = TreeNode(6);
tree.root?.left?.left?.left = TreeNode(4);
tree.root?.right = TreeNode(10);
tree.root?.right?.right = TreeNode(6);
tree.root?.right?.right?.left = TreeNode(2);
/*
(15 & -4 & 6 & 4 ) = 4
(15 & -4 & 12 & 6 & 9) = 0
(15 & -4 & 12 & 8) = 8
(15 & 10 & 6 & 2 ) = 2
Result is : 8
*/
tree.pathBitwiseAND();
}input
Maximum Bitwise AND : 8
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