Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
3.
Approach
3.1.
Code in C++
3.2.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
In a binary tree, what is the maximum number of leaves?
4.2.
What is the difference between logical AND and Bitwise AND?
4.3.
How is stack used in memory management?
5.
Conclusion
Last Updated: Mar 27, 2024

How to Find the Maximum Value of Bitwise AND from Root to Leaf in a Binary tree?

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Before jumping to the question let's first know what the Bitwise AND operator are. 

The bitwise AND (&) is a binary operation that gives binary representation 1 (1*1=1) if both the bits are 1 otherwise the result is 0 (0*0=0, 1*0=0).

A B A & B
0 0 0
0 1 0
1 0 0
1 1 1

 

Problem statement

We are given a Binary tree. Our goal is to find the maximum Bitwise AND of all nodes in any path from the root to the leaf node.

Example:

Input1: 

 

Binary Tree

 

Output1: 16

 

Explanation:  

Path1: (17 & 5 & 7 & 13) = 1

 

Binary Tree

 

Path2: (17 & 5 & 7 & 9) = 1

 

Binary Tree

 

Path3: (17 & 20 & 11) = 0

Binary Tree

 

Path4: (17 & 20 & 19) = 16  // maximum value of Bitwise AND from root to leaf 

 

Binary Tree

 

Input 2:  

 

Binary Tree

 

Output2: 1

 

Explanation: 

 

Path1: (5 & 7 & 9) = 1 // maximum value of Bitwise AND from root to leaf 

 

Binary Tree

Also see, Data Structures

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

The idea is simple, traverse through every path from the root to leaf in the given binary tree and calculate the bitwise AND of all the nodes that occurred in the paths one by one. Finally, calculate the maximum of all these values.

Steps:

  • Declare a global variable MAX_AND = 0, which stores the maximum value of Bitwise AND from root to leaf.
  • Declare a curr_ans variable in the main function and initialise with root->data.
  • Now, inside the maximum_AND function, if root=NULL return.
  • Else check if it is a leaf node then do curr_ans = (curr_ans & root->data), take maximum of curr_ans and MAX_AND and return.
  • Else call recursively for the left and right subtree and replace the curr_ans parameter from (curr_ans & root->data).
     

Let’s understand the above approach with an example:


Input:



 

So, initially MAX_AND = 0, curr_ans = root->data. We start traversing all the paths one by one. If we reach any leaf node, we calculate the Bitwise AND of all the path nodes and take the maximum from all the paths.

 

  • MAX_AND = 0, curr_ans = 15 // root data

 

 

  • MAX_AND = 0, curr_ans = (15 & 13)=13.


     



 

  • Now, we encountered a leaf node, curr_ans = (15 & 13 & 4) = 4, MAX_AND = max(4, 0) = 4.

 

 

  • Again, we encountered a leaf node, curr_ans = (15 & 13 & 17) = 1, MAX_AND = max(1, 4) = 4.

 




 

 

  • MAX_AND = 4, curr_ans = ( 15 & 7) = 7. 

 

 

  • We encountered a leaf node, curr_ans = ( 15 & 7 & 19) = 3, MAX_AND = (3,4) = 4.

 

 

Finally, print the MAX_AND = 4which is the maximum value of Bitwise AND from root to leaf. 

 

Code in C++

#include <bits/stdc++.h>
using namespace std;

int MAX_AND = 0;

struct Node {
  int data;

  Node *left, *right;

  Node(int x)
  {
      data = x;
      left = NULL;
      right = NULL;
  }
};


void maximum_AND(Node* root, int curr_ans)
{

  if (root == NULL)
      return;

  if (root->left == NULL
        && root->right == NULL) {
      curr_ans = curr_ans & root->data;

      MAX_AND = max(curr_ans, MAX_AND);

      return;
  }

  maximum_AND(root->left,
              curr_ans & root->data);

  maximum_AND(root->right,
              curr_ans & root->data);
}

int main()
{
  
  Node* root = new Node(17);
  root->left = new Node(5);
  root->right = new Node(20);
  root->left->left = new Node(7);
  root->left->left->left = new Node(13);
  root->left->left->right = new Node(7);
  root->right->left = new Node(11);
  root->right->right = new Node(19);

  maximum_AND(root, root->data);

  cout << MAX_AND << endl;

  return 0;
}

 

Output

16

Complexity Analysis

Time complexity: O(n), where n is the number of nodes in the given tree as we are traversing all the nodes.

Space complexity: O(h), where h is the height of the given binary tree.

Check out this problem - Root To Leaf Path

Frequently Asked Questions

In a binary tree, what is the maximum number of leaves?

The maximum number of leaves in a node binary tree is 2^(h+1)-1, where h is the tree's height. The more leaf nodes a tree has, the more balanced it is. A tree that is completely skewed to one side will only have one leaf. As an example, if you have a fully balanced tree with n nodes, the height will be (log 2n), and the number of leaves will be 2^(log2n - 1).

What is the difference between logical AND and Bitwise AND?

The logical AND operator returns only Boolean values when applied to Boolean expressions. The bitwise AND operator accepts and returns data of the types integer, short int, long, and unsigned int.

How is stack used in memory management?

A stack is a memory section in a computer that keeps temporary variables generated by a function. Variables are declared, stored, and initialised in the stack during runtime. It's a type of transient memory. The memory of the variable will be automatically wiped once the computational process is completed. 

Conclusion

So, this article discussed the Bitwise AND(&) and the problem of finding the maximum value of Bitwise AND from root to leaf in a Binary tree with examples for better understanding and its implementation in C++.

If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free! 

Recommended Reading:

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Thank you for reading!

Previous article
Maximum Absolute Difference between any Two Levels of Binary Tree
Next article
Print the Longest Path from the Root to Leaf in a Binary Tree
Live masterclass