Skip to main content

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 : 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




Comment

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