## Pseudocode

- Do a postorder traversal.
- Write the base case, if root is null then return.
- First recur on left child.
- Then recur on right child.
- If both children are not null then take their logical AND value and change the value of root node.
- Repeat the process until you reach the head node

## Implementation in Java

```
class Test {
public static class Node {
int val;
Node left;
Node right;
}
// creating a new node
static Node newNode(int data) {
Node root = new Node();
root.val = data;
root.left = null;
root.right = null;
return root;
}
// Doing a postorder traversal
static void convertBT(Node node) {
if (node == null)
return;
convertBT(node.left);
convertBT(node.right);
if (node.left != null && node.right != null) {
node.val = (node.left.val) & (node.right.val); // converting root based on
// AND values of left and right trees.
}
}
// to print the tree
static void printBT(Node node) {
if (node == null)
return;
printBT(node.left);
System.out.print(node.val + " ");
printBT(node.right);
}
// main function
public static void main(String[] args) {
Node root = newNode(1);
root.left = newNode(0);
root.right = newNode(1);
root.left.left = newNode(1);
root.left.right = newNode(0);
root.right.left = newNode(1);
root.right.right = newNode(0);
System.out.print("Before: ");
printBT(root); // printing before tree
convertBT(root);
System.out.println();
System.out.print("After: ");
printBT(root); // printing after tree
}
}
```

**Output: **

```
Before: 1 0 0 1 1 1 0
After: 1 0 0 0 1 0 0
```

### Implementation in C++

```
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* left;
struct Node* right;
};
// function to create a new node
struct Node* newNode(int val)
{
struct Node* node = new Node;
node->data= val;
node->left = node->right = NULL;
return node;
}
void convertBTree(Node *node)
{
if (node == NULL)
return;
convertBTree(node->left);
convertBTree(node->right);
if (node->left != NULL && node->right != NULL){
node->data = (node->left->data) & (node->right->data); // converting root based on
// AND values of left and right trees.
}
}
void printInorder(Node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
void solve(){
Node *root=newNode(0);
root->left=newNode(1);
root->right=newNode(1);
root->left->left=newNode(1);
root->left->right=newNode(0);
root->right->left=newNode(1);
root->right->right=newNode(0);
printf("\n Before: ");
printInorder(root); //printing before tree
convertBTree(root);
printf("\n After: "); //printing after tree
printInorder(root);
}
// main function
int main()
{
solve();
return 0;
}
```

**Output: **

```
Before: 1 0 0 1 1 1 0
After: 1 0 0 0 1 0 0
```

### Complexity Analysis

**Time complexity:** O(n) We traverse each node once

**Space Complexity: **O(1), Not using any extra space

Check out this problem - __Diameter Of Binary Tree__

## Frequently Asked Questions

### What are the features of BST?

The 2 features of A binary search tree (BST) are

- Each node has a maximum of two children.
- For each node, the values of its left child nodes are less than that of the present or current node, which in turn is less than the right child nodes (if any).

### What does time complexity mean?

The time complexity in computer science is the computational complexity that describes how long it takes a computer to run an algorithm. Choosing the most efficient algorithm is always better when a fundamental problem can be solved using multiple methods.

### What does space complexity mean?

The space complexity of an algorithm is the total space taken by the algorithm with respect to the input size. In simple words, An algorithm's amount of memory is known as its space complexity.

### What are the limitations of the Binary search algorithm?

The limitations of the Binary Search Algorithm are

- It uses a recursive approach which requires more stack space.
- Programming binary search algorithm is difficult and error-prone.
- The interaction of this algorithm with memory hierarchy (caching) is poor.

### List some types of binary trees.

Some types of Binary trees are

- Full Binary Tree.
- Perfect Binary Tree.
- Complete Binary Tree.
- Degenerate or Pathological Tree.
- Skewed Binary Tree.
- Balanced Binary Tree.

## Conclusion

This article discussed the solution for converting a given Binary tree to a tree that holds Logical AND property along with its different approaches, pseudocode, implementation, and code in both JAVA and C++.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in __Data Structures and Algorithms__, __Competitive Programming__, __JavaScript__, __System Design__, __Machine learning__ and many more! If you want to test your competency in coding, you may check out the mock __test series__ and participate in the __contests__ hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the__ problems__, __interview experiences__, and __interview bundle__ for placement preparations.

Nevertheless, you may consider our paid __courses__ to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!