Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
3.
Pseudocode
4.
Implementation in Java
4.1.
Implementation in C++
4.2.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What are the features of BST?
5.2.
What does time complexity mean?
5.3.
What does space complexity mean?
5.4.
What are the limitations of the Binary search algorithm?
5.5.
List some types of binary trees.
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

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

Introduction

This article will look at the problem of converting a given Binary tree to a tree that holds Logical AND property. Binary tree questions are the most popular and vital in coding interviews and programming competitions. Let's understand the problem statement.

In computer science, a binary tree, by definition, is a tree data structure in which each node has at most 2 children, referred to as the left child and the right child.

Binary Tree example

Also See, Binary Tree Postorder Traversal.

Problem Statement

We are given a binary tree each node having a value of only 0 or 1. We have to write a program to convert the tree that holds Logical AND property, i.e., each node value should be the logical AND of its children.

Sample Examples

Example 1

Input:    
             0
           /   \
          0     1
               / \
              0   1


Output:    
             0
           /   \
          0     0
               / \
              0   1


Explanation: Since the input tree is not logical AND of its below two children, we will convert the tree as in output. For this, we begin from the last level, we have 0 and 1 whose AND value is 0. So we get the above level as 1 and 1. On taking AND of these two numbers we get 1 which forms the required tree.

 

Example 2

Input:    
             0
           /   \
          1     1
         /  
        1     
        
Output:  
             0
           /   \
          1     1 
         / 
        1   
        
Explanation: Since the last level has only 1, the AND value becomes 1 in the above level. So we get 1 and 1. On taking AND of these two we get all 1s.

Approach

In this method, we will traverse the binary tree in a postorder fashion as in postorder traversal both the children of the root have already been visited before the root itself. For each node check (recursively) if the node has one child then we don’t have any need to check else if the node has both its child then simply update the node data with the logical AND of its child data.  

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

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

  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 AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine 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 problemsinterview 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!!

Previous article
Convert a Generic Tree (n-ary tree) to Binary Tree
Next article
Convert left-right representation of a binary tree to down-right
Live masterclass