Posted on by Kalkicode
Code Recursion

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:

  1. 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.
  2. 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.
  3. 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

  1. The maximumBitwiseAND function recursively traverses the binary tree and computes the maximum bitwise AND value along each path.
  2. In the pathBitwiseAND function, the initial result is set to the minimum possible integer value. Then, the maximumBitwiseAND function is called with the root node, the value of the root node, and the result variable.
  3. 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.

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