Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approaches
2.1.
Approach 1
2.2.
Approach 2
3.
Frequently Asked Questions
3.1.
What does it mean to fold a binary tree? 
3.2.
Is there symmetry in trees? 
3.3.
In a binary search tree, what is the difficulty of deletion? 
3.4.
Is the AVL tree or the B-tree better?  
3.5.
What is a node's number of subtrees? 
4.
Conclusion
Last Updated: Mar 27, 2024

Foldable Binary Tree

Introduction

If the left and right subtrees of a binary tree are mirror images of each other, the tree can be folded. An empty tree can also be folded. Because both binary trees have a left subtree that is the mirror image of the right subtree, they can be folded.

Approaches

  1. Change the left subtree to its mirrored counterpart. After that, see if the mirror is the same as the right subtree. 
     
  2. Check to see if the right and left subtrees are mirror images of each other.

Approach 1

  1.  If the tree is empty, return true. 
     
  2. Create a mirror replica of the left subtree. 
     
  3. Return true if the right subtree is equivalent to the mirror image; otherwise, return false.
     
void Check(node* Node)
{
    if ( Node == NULL )
        return;
    else {
        node* temp;
        Check( Node–>left );
        Check( Node–>right );


        temp = Node–>left;
        Node–>left = Node–>right;
        Node–>right = temp;
    }
}

Approach 2

 In the check(a,b) function: 

  1. If both trees are empty, true is returned. 
     
  2. Return false if only one of them is empty. 
     
  3. Return true if one subtree is a mirror of another.
     
bool Check(node* x1, node* x2)
{
    if (x1 == NULL && x2 == NULL) {
        return true;
    
}
    if (x1 == NULL || x2 == NULL) {
        
return false;
    
}
    
return Check(x1–>left, x2–>right)
           
&& Check(x1–>right, x2–>left);
}


foldable(a) function: 

  • We'll verify if the trees are null first, then return true if they are. 
     
  • Otherwise, use the check function to see if the left and right subtrees are mirror images of each other.
     
bool dofoldable(node* root)
{
    if (root == NULL) {
       
return true;
    
}
 
    return Check(root–>left, root–>right);
}

Must Recommended Topic, Binary Tree Postorder Traversal.

Frequently Asked Questions

What does it mean to fold a binary tree? 

If the left and right subtrees are mirror images of each other, the tree can be folded. An empty tree can also be folded. Because both binary trees have a left subtree, the mirror image of the right subtree can be folded.

Is there symmetry in trees? 

The tree has a symmetric structure if the left and right subtrees mirror one other. If all of the following requirements are met, two trees will mirror each other: Both trees are either empty or not empty. The mirror image of the right subtree is the left subtree.

In a binary search tree, what is the difficulty of deletion? 

Time complexity is O in general (h). Deleting element 1 necessitates a traversal of all elements to locate it (in orders 3, 2, 1). As a result, deletion in a binary tree has an O worst-case complexity (n). Time complexity is O in general (h).

Is the AVL tree or the B-tree better?  

AVL trees are designed for usage in memory, where random access is inexpensive. Because they aggregate a higher number of keys into each node, B-trees are better suitable for disk-backed storage because they reduce the number of seeks required by a reading or write operation.

What is a node's number of subtrees? 

The degree of a node is the number of subtrees it has. Node A, for example, has a degree of three, while node E has a degree of two. The degree of the tree is the maximum degree of all nodes.

Conclusion

This article has gone through the foldable binary tree. We may simply determine whether a binary tree is foldable or not using either of the methods above. You may also CheckOut our course on the tree.

Recommended problems -

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Ninja, have a great time learning.

Live masterclass