Maximum Bitwise AND value in binary tree path from root to leaf nodes
The problem involves finding the maximum bitwise AND value along any path from the root to a leaf node in a binary tree. The goal is to determine the path that, when performing bitwise AND operations on its nodes, results in the highest possible value.
Problem Statement
Given a binary tree, the task is to find the path from the root to a leaf node such that performing bitwise AND operations on its nodes results in the maximum possible value. The program should print this maximum bitwise AND value.
Example
Consider the binary tree given in the code:
15
/ \
-4 10
/ \ \
6 12 6
/ / \ /
4 6 8 2
/
9
For this tree, the maximum bitwise AND value along any path from the root to a leaf node is 8.
Idea to Solve
The problem can be solved using a recursive approach. The maximumBitwiseAND
function recursively
traverses the binary tree and computes the maximum bitwise AND value along each path from the root to a leaf node.
It uses a variable to keep track of the maximum bitwise AND value encountered so far.
During traversal, the following steps are performed:
- If the current node is a leaf node, perform the bitwise AND operation with the current value and update the result if the new result is greater.
- If the bitwise AND operation of the current node's value with the current value is less than or equal to the current result, stop further traversal along this path.
- Otherwise, continue traversing the left and right subtrees with the updated value.
Pseudocode
function maximumBitwiseAND(node, value, result):
if node is not null:
if node is a leaf node:
update result if (value AND node.data) > result
else if (value AND node.data) <= result:
return
else:
maximumBitwiseAND(node.left, value AND node.data, result)
maximumBitwiseAND(node.right, value AND node.data, result)
function pathBitwiseAND(node):
if node is null:
return
initialize result as INT_MIN
call maximumBitwiseAND with root node, node.data, and result
print Maximum Bitwise AND: result
main:
create binary tree
construct tree as shown
call pathBitwiseAND with root node
Algorithm Explanation
- The
maximumBitwiseAND
function recursively traverses the binary tree and computes the maximum bitwise AND value along each path. - In the
pathBitwiseAND
function, the initial result is set to the minimum possible integer value. Then, themaximumBitwiseAND
function is called with the root node, the value of the root node, and the result variable. - After traversal, the calculated maximum bitwise AND value is printed.
Code Solution
// 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 : 8
import 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
Time Complexity
The time complexity of the solution is proportional to the number of nodes in the binary tree since each node is visited once during the traversal. In the worst case, the time complexity is O(n), where n is the number of nodes in the binary tree.
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