Check if Two Binary Trees have Same Structure

Given a Binary Tree, the task is to Check if Two Binary Trees have Same Structure

Two trees are considered the same as each other if:

The structure (or shape) of the trees is identical. This means:
- The left subtree of the first tree should be the same as the right subtree of the second tree.
- The right subtree of the first tree should be the same as the left subtree of the second tree.
The values of the nodes are not necessary to be the same i.e., it is only the structure that matters, not the data in the nodes.

Code Flow for Check if Two Binary Trees Have Same Structure

The function checkSameStructure checks if the two binary trees rooted at node1 and node2 are the same images of each other.
Base Case 1: If both node1 and node2 are null, it returns true because both trees are empty and thus same images.
Base Case 2: If one of the nodes is null and the other is not, it returns false because one tree is empty, and the other is not.
Recursive Step: It recursively checks:
- The left subtree of node1 against the right subtree of node2.
- The right subtree of node1 against the left subtree of node2.
Both conditions must be true for the trees to be the same as each other.

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 checkSameStructure(Node node1, Node node2) {
        /*  If both node1 and node2 are null, it means both trees are empty or we’ve reached the end of both trees at the same level.   */
        if (Objects.isNull(node1) && Objects.isNull(node2)) {
            System.out.println("BinarySearchTree.checkSameStructure both nodes are null");
            return true;
        }
        /*  If only one of the nodes (node1 or node2) is null, it means the trees are not same images, because a tree cannot be a same of another if one of the trees is missing a node at any corresponding position.  */
        if (Objects.isNull(node1) || Objects.isNull(node2)) {
            System.out.println("BinarySearchTree.checkSameStructure 1 of the node is null");
            return false;
        }
        /*  checks if the left subtree of node1 is a same of the left subtree of node2, and if the right subtree of node1 is a same of the right subtree of node2.  */
        return checkSameStructure(node1.left, node2.left) && checkSameStructure(node1.right, node2.right);
    }

    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.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;
import static org.wesome.dsalgo.BinarySearchTree.checkSameStructure;

public class BinaryTreeTest {

    @Test
    public void testBothTreesAreNull() {
        assertTrue(checkSameStructure(null, null), "Both trees are null, should return true");
    }

    @Test
    public void testOneTreeIsNull() {
        Node tree1 = new Node(1);
        Node tree2 = null;
        assertFalse(checkSameStructure(tree1, tree2), "One tree is null, should return false");
    }

    @Test
    public void testBothTreesAreSingleNodes() {
        Node tree1 = new Node(1);
        Node tree2 = new Node(1);
        assertTrue(checkSameStructure(tree1, tree2), "Both trees are single nodes with the same value, should return true");
    }

    @Test
    public void testTreesWithDifferentRootValues() {
        Node tree1 = new Node(1);
        Node tree2 = new Node(1);
        assertTrue(checkSameStructure(tree1, tree2), "Trees with different root values, but same structure should return true");
    }

    @Test
    public void testTreesWithSingleSubtree() {
        Node tree1 = new Node(1);
        tree1.left = new Node(2);
        Node tree2 = new Node(1);
        tree2.right = new Node(2);
        assertFalse(checkSameStructure(tree1, tree2), "Both trees have one subtree, should return false");
    }

    @Test
    public void testTreesAreSamesOfEachOther() {
        Node rootA = new Node(10);
        rootA.left = new Node(5);
        rootA.right = new Node(15);
        rootA.left.left = new Node(2);
        rootA.left.right = new Node(7);
        rootA.right.left = new Node(12);
        rootA.right.right = new Node(18);

        Node rootB = new Node(10);
        rootB.right = new Node(5);
        rootB.left = new Node(15);
        rootB.right.right = new Node(2);
        rootB.right.left = new Node(7);
        rootB.left.right = new Node(12);
        rootB.left.left = new Node(18);
        assertTrue(checkSameStructure(rootA, rootB), "Both trees are sames of each other, should return true");
    }

    @Test
    public void testTreesWithDifferentStructures() {
        Node rootA = new Node(10);
        rootA.left = new Node(5);
        rootA.right = new Node(15);
        rootA.left.left = new Node(2);
        rootA.left.right = new Node(7);
        rootA.right.left = new Node(12);
        rootA.right.right = new Node(18);

        Node rootB = new Node(1);
        rootB.right = new Node(2);
        rootB.left = new Node(3);
        rootB.right.right = new Node(4);
        rootB.right.right.right = new Node(5);
        rootB.right.right.left = new Node(6);
        rootB.right.left = new Node(7);
        rootB.right.left.right = new Node(8);
        rootB.right.left.left = new Node(9);
        rootB.left.right = new Node(10);
        rootB.left.left = new Node(11);
        assertFalse(checkSameStructure(rootA, rootB), "Trees with different structures, should return false");
    }

    @Test
    public void testTreesWithAdditionalNode() {
        // Constructing the following tree:
        //       1
        //      / \
        //     2   3
        //    / \
        //   4   5

        Node rootA = new Node(1);
        rootA.left = new Node(2);
        rootA.right = new Node(3);
        rootA.left.left = new Node(4);
        rootA.left.right = new Node(5);

        // Constructing the following tree:
        //       10
        //      / \
        //     20   30
        //    / \
        //   40   50
        //         \
        //          60

        Node rootB = new Node(10);
        rootB.left = new Node(20);
        rootB.right = new Node(30);
        rootB.left.left = new Node(40);
        rootB.left.right = new Node(50);
        rootB.left.right.right = new Node(60);
        assertFalse(checkSameStructure(rootA, rootB), "Trees with symmetric structure, should return true");
    }


    @Test
    void testTreeWithSameValues() {
        // Constructing the following tree:
        //          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(checkSameStructure(root, root), "Same Trees, should return true");
    }


    @Test
    void testSkewedTree() {
        // Constructing the following tree:
        //          10
        //           \
        //            20
        //             \
        //              30
        //               \
        //                40
        //                 \
        //                  50

        //                  10
        //                 /
        //                20
        //               /
        //              30
        //             /
        //           40
        //          /
        //         50

        Node rootA = new Node(10);
        rootA.right = new Node(20);
        rootA.right.right = new Node(30);
        rootA.right.right.right = new Node(40);
        rootA.right.right.right.right = new Node(50);

        Node rootB = new Node(10);
        rootB.left = new Node(20);
        rootB.left.left = new Node(30);
        rootB.left.left.left = new Node(40);
        rootB.left.left.left.left = new Node(50);
        assertFalse(checkSameStructure(rootA, rootB), "Skewed Trees, should return false");
    }
}

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:

The time complexity is O(n), where n is the number of nodes in the trees. This is because we visit each node once during the recursion.

Space Complexity:

The space complexity is O(h), where h is the height of the tree. This is because of the recursive stack used for the function calls.

Check if Two Binary Trees have Same Structure

Code Flow for Check if Two Binary Trees Have Same Structure

Complexity Analysis

Time Complexity:

Space Complexity:

follow us on