Given a Binary Tree, the task is to Check if Binary Tree is Foldable Tree. A foldable binary tree is a binary tree where the left and right subtrees of every node are mirror images of each other. In other words, if you "fold" the left subtree over the right subtree like folding a piece of paper, the tree should still maintain its structure.
Code Flow for Check if Binary Tree Is Foldable Tree
-
If the root is
null, the tree is considered foldable, so it returnstrue. - If the root is not
null, it calls theisMirrormethod with the left and right children of the root node to check if the left and right subtrees are mirror images of each other. - Takes two
Nodeobjects,node1andnode2, which represent the two subtrees to be checked for mirroring.-
Both nodes are
null: If bothnode1andnode2arenull, it means both subtrees are empty, or we've reached the end of both subtrees at the same level. In this case, it prints a log message and returnstrue. -
One node is
null: If only one of the nodes isnull, the subtrees are not mirror images of each other because one subtree is missing a node at a corresponding position. It prints a log message and returnsfalse. -
Recursive mirror check: If neither node is
null, the method recursively checks:-
The left subtree of
node1against the right subtree ofnode2. -
The right subtree of
node1against the left subtree ofnode2. This ensures the trees are mirrored at each level.
-
-
Let's see the code now
package org.wesome.dsalgo;
import lombok.Data;
import java.util.Objects;
public class BinarySearchTree {
Node root;
public static boolean isFoldableTree(Node node) {
/* If root is null, they are Fold ableTree, so the method returns true. */
if (Objects.isNull(node)) {
System.out.println("BinarySearchTree.isFoldableTree node is null, hence tree is foldable, hence returns true.");
return true;
}
return isMirror(node.left, node.right);
}
static boolean isMirror(Node node1, Node node2) {
/* If both node1 and node2 are null, it means both subtrees are empty or we've reached the end of both subtrees at the same level. In this case, it prints a log message and returns true. */
if (Objects.isNull(node1) && Objects.isNull(node2)) {
System.out.println("BinarySearchTree.isMirror both nodes are null");
return true;
}
/* If only one of the nodes is null, the subtrees are not mirror images of each other because one subtree is missing a node at a corresponding position. It prints a log message and returns false. */
if (Objects.isNull(node1) || Objects.isNull(node2)) {
System.out.println("BinarySearchTree.isMirror 1 of the node is null");
return false;
}
/* checks if the left subtree of node1 is a same of the right subtree of node2, and if the right subtree of node1 is a same of the left subtree of node2. */
return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
}
void insert(int data) {
System.out.println("BinarySearchTree.insert data = " + data);
root = insert(root, data);
}
Node insert(Node root, int data) {
if (Objects.isNull(root)) {
Node tempNode = new Node(data);
return tempNode;
}
if (data > root.data) {
root.right = insert(root.right, data);
} else {
root.left = insert(root.left, data);
}
return root;
}
}
@Data
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertTrue;
import static org.wesome.dsalgo.BinarySearchTree.isFoldableTree;
public class BinaryTreeTest {
@Test
void testNullTree() {
Node root = null;
assertTrue(isFoldableTree(root), "Expected tree to be foldable (null tree).");
}
@Test
void testSingleNodeTree() {
Node root = new Node(1);
assertTrue(isFoldableTree(root), "Expected tree with a single node to be foldable.");
}
@Test
void testFoldableTree() {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(2);
root.left.left = new Node(3);
root.left.right = new Node(4);
root.right.left = new Node(4);
root.right.right = new Node(3);
assertTrue(isFoldableTree(root), "Expected tree to be foldable.");
}
@Test
void testNonFoldableTree() {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
assertTrue(isFoldableTree(root), "Expected tree to be non-foldable.");
}
@Test
void testTreeWithNullSubtrees() {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(2);
root.left.left = null;
root.left.right = new Node(3);
root.right.left = new Node(3);
root.right.right = null;
assertTrue(isFoldableTree(root), "Expected tree to be foldable with null subtrees.");
}
@Test
void testComplexNonFoldableTree() {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
assertTrue(isFoldableTree(root), "Expected complex tree to be non-foldable.");
}
@Test
void testTreeWithSameValues() {
// 1
// / \
// 1 1
// / \ / \
// 1 1 1 1
Node root = new Node(1);
root.left = new Node(1);
root.right = new Node(1);
root.left.left = new Node(1);
root.left.right = new Node(1);
root.right.left = new Node(1);
root.right.right = new Node(1);
assertTrue(isFoldableTree(root), "Same Trees, should return true");
}
}
plugins {
id("java")
id("io.freefair.lombok") version "8.13"
}
group = "org.wesome.dsalgo"
version = "1.0-SNAPSHOT"
repositories {
mavenCentral()
}
dependencies {
testImplementation(platform("org.junit:junit-bom:5.10.0"))
testImplementation("org.junit.jupiter:junit-jupiter")
}
tasks.test {
useJUnitPlatform()
}Complexity Analysis
Time Complexity:
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity:
Space Complexity: O(h), where h is the height of the tree (which could be O(log n) for balanced trees or O(n) for skewed trees).
