Convert a given Binary tree to a tree that holds Logical AND property

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

You can also try this code with Online Java Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

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

1. Each node has a maximum of two children.
2. 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

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

List some types of binary trees.

Some types of Binary trees are

1. Full Binary Tree.
2. Perfect Binary Tree.
3. Complete Binary Tree.
4. Degenerate or Pathological Tree.
5. Skewed Binary Tree.
6. 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!!