Objective: Given Two binary Search Trees, Check if both are identical.
Input: Two binary Search Trees
Approach:
- Travesre both trees at the same time, starting from root.
- Check if roots are not null and data are matched, if not, return false.
- Make recursice calls to root.left and root.right.
- If any of the tree gets over and other is not , return false.
- if both traversal of both trees ends at the same time, return true
- see code.
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class TwoIdenticalBST { | |
| public boolean identicalBSTs(Node rootA, Node rootB){ | |
| if((rootA==null)&&(rootB==null)){ | |
| return true; | |
| }else if((rootA!=null && rootB==null)||(rootA==null && rootB!=null)){ | |
| return false; | |
| }else if(rootA.data==rootB.data){ | |
| return identicalBSTs(rootA.left, rootB.left) && identicalBSTs(rootA.right, rootB.right); | |
| }else{ | |
| return false; | |
| } | |
| } | |
| public static void main(String args[]){ | |
| BST a = new BST(); | |
| a.insert(2);a.insert(4);a.insert(1);a.insert(3);a.insert(5); | |
| BST b = new BST(); | |
| b.insert(2);b.insert(4);b.insert(1);b.insert(3);b.insert(5); | |
| TwoIdenticalBST t = new TwoIdenticalBST(); | |
| System.out.println(t.identicalBSTs(a.root, b.root)); | |
| a.insert(11);b.insert(12); | |
| System.out.println(t.identicalBSTs(a.root, b.root)); | |
| } | |
| } | |
| class Node{ | |
| int data; | |
| Node left; | |
| Node right; | |
| public Node(int data){ | |
| this.data = data; | |
| left = null; | |
| right = null; | |
| } | |
| } | |
| class BST{ | |
| public Node root=null; | |
| public boolean find(int id){ | |
| Node current = root; | |
| while(current!=null){ | |
| if(current.data==id){ | |
| return true; | |
| }else if(current.data>id){ | |
| current = current.left; | |
| }else{ | |
| current = current.right; | |
| } | |
| } | |
| return false; | |
| } | |
| public void insert(int id){ | |
| Node newNode = new Node(id); | |
| if(root==null){ | |
| root = newNode; | |
| return; | |
| } | |
| Node current = root; | |
| Node parent = null; | |
| while(true){ | |
| parent = current; | |
| if(id<current.data){ | |
| current = current.left; | |
| if(current==null){ | |
| parent.left = newNode; | |
| return; | |
| } | |
| }else{ | |
| current = current.right; | |
| if(current==null){ | |
| parent.right = newNode; | |
| return; | |
| } | |
| } | |
| } | |
| } | |
| } |
Output-
true false