Write a simple program to identify given two binary trees are mirrored image of each other. Here is an example image of mirrored trees:
Here are the steps to find out mirrored binary trees:
- If both given trees root node values are same.
- Left subtree of root of first tree is mirror of right subtree of root of second tree.
- Right subtree of root of first tree is mirror of left subtree of root of second tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | package com.java2novice.ds.trees; public class MirrorTreesEx { public static boolean areMirrorTrees(Node a_root, Node b_root) { /** * Recursion exist condition - 1 * When both nodes are null, return true */ if(a_root == null && b_root == null) { return true; } /** * Recursion exist condition - 2 * When one of the node is null, return false */ if(a_root == null || b_root == null) { return false; } return a_root.data == b_root.data && areMirrorTrees(a_root.left, b_root.right) && areMirrorTrees(a_root.right, b_root.left); } public static void main(String arg[]) { BinaryTree a = new BinaryTree(); a.root = new Node(5); a.root.left = new Node(6); a.root.right = new Node(7); a.root.left.left = new Node(8); a.root.left.right = new Node(9); BinaryTree b = new BinaryTree(); b.root = new Node(5); b.root.left = new Node(7); b.root.right = new Node(6); b.root.right.left = new Node(9); b.root.right.right = new Node(8); System.out.println("Is Mirror Trees? "+MirrorTreesEx.areMirrorTrees(a.root, b.root)); BinaryTree a1 = new BinaryTree(); a1.root = new Node(5); a1.root.left = new Node(6); a1.root.right = new Node(7); a1.root.left.left = new Node(8); a1.root.left.right = new Node(9); BinaryTree b1 = new BinaryTree(); b1.root = new Node(5); b1.root.left = new Node(7); b1.root.right = new Node(6); b1.root.right.left = new Node(9); System.out.println("Is Mirror Trees? "+MirrorTreesEx.areMirrorTrees(a1.root, b1.root)); } } |
Output:
1 2 3 4 | Is Mirror Trees? true Is Mirror Trees? false |
