Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Given a Binary Tree, we will develop an algorithm to check if it has duplicate values. This can be done in linear time O(N) where there are N elements in the Binary Tree.
First things first,What is a Binary tree exactly?
A binary tree is a tree-type non-linear data structure.Each node of a binary tree has maximum of two children and minimum of zero children. The node at the top of the hierarchy of a tree is called the root node.Each node has at most two children which are referred to as the right child and left child.
In this article,we will understand how to check if any two nodes in a given tree have the same data value(duplicate value).
In the tree given below,two nodes have the same value of 6 and therefore,our code should return true.
6
/ \
10 9
/ \ / \
12 6 5 4
In case of Linear data structures,we can simply traverse them in one way and check if two values are same.Trees are non linear data structures and it therefore has multiple ways of traversal.The multiple ways of traversal can be checked out in this article.
A simple way to find out if the trees has two nodes that have same data value is to traverse the tree and store the value in an Array List and then checking if the Array List has any entries that have the same value.
To traverse the tree,we can use any of the following:
- Inorder traversal
- Preorder traversal
- Postorder traversal
In this article we will be using Preorder traversal, a traversal in which root is visited first then the left subtree and later the right subtree.While traversing,we store the value of the nodes in an Array List and then it can be check if Array List contains any duplicate elements.There are various ways of checking if Array List has duplicate elements,an O(n^2) approach is discussed below.
Note: We are using Array List since the number of nodes in the tree are unknown(we don't require to specify size for an Array List during its initialization),an array can also be used if number of nodes is known beforehand or we can traverse the tree once to find out total number of nodes so that we are able to specify size of array that will store the data values.
import java.util.*;
public class Duplicates {
public static void main(String[] args)
{
/*
6
/ \
10 9
/ \ / \
12 6 5 4
*/
Node root=new Node(6);
root.left=new Node(10);
root.right=new Node(9);
root.left.left=new Node(12);
root.left.right=new Node(6);
root.right.left=new Node(5);
root.right.right=new Node(4);
ArrayList<Integer> arr=new ArrayList<Integer>();
traversal(root,arr);
boolean flag=false;
for(int i=0;i<arr.size();i++)
{
for(int j=i+1;j<arr.size();j++)
{
if(arr.get(i)==arr.get(j))
{
flag=true;
break;
}
}
}
System.out.println(flag);
}
private static void traversal(Node root, ArrayList<Integer> arr) {
if(root==null)
{return;}
arr.add(root.data);// as root is not null add its data value to List
traversal(root.left,arr);
traversal(root.right,arr);
}
}
class Node
{
// Node has data,pointer to left and right child
int data;
Node left,right;
Node(int value)
{
this.data=value;
}
}
Note:
- Time Complexity:O(n^2)+O(n)=O(n^2)
(O(n^2) is required to check for duplicates in the ArrayList as there are nested for loops,it takes a total of O(n^2) time and O(n) is required for tree traversal as there are a total of n nodes to be traversed.O(n^2) is the dominant term,thus O(n^2)+O(n)=O(n^2) - Space Complexity:O(n)
(Size of Array List is n as it stores the total number of nodes in tree)
We can reduce the time for finding duplicates to O(n) by using Hash Map but even then we are traversing the Array List at least once.
A better way is to use a Hash Map and avoid use of Array List all together and traverse the tree only once.This way the problem can be solved in O(n) time.
Approach: We traverse the given tree, for every node, we check if it's data value already exists in the Hash Map.If it does not exist,then we put it into the Hash Map.If it exists already i.e. there is a duplicate and we return true.To check if an element exists in Hash Map already,it only takes O(1) time.
6
/ \
10 9
/ \ / \
12 6 5 4
For example,In the given tree above,we traverse using preorder traversal.So when we start,we check if root i.e 6 is present in HashMap already as it is not we put it in the HashMap,next we go to 10 according to preorder and check if its present,if not we put in the HashMap, and so on.When we come to the 6 which is the right child of 10 ,we check if it is present in the map already and we find that it is,as we already have put 6 in the map because 6 was the root element and therefore we have found a duplicate and we return true.Suppose you have a tree which has no duplicates then we keep putting elements in the map and finally when we have traversed the whole tree,false is returned.
package Open;
import java.util.*;
public class Duplicates {
public static void main(String[] args)
{
/*
6
/ \
10 9
/ \ / \
12 6 5 4
*/
Node root=new Node(6);
root.left=new Node(10);
root.right=new Node(9);
root.left.left=new Node(12);
root.left.right=new Node(6);
root.right.left=new Node(5);
root.right.right=new Node(4);
HashMap<Integer,Integer> map=new HashMap<Integer,Integer> ();
System.out.println(traversal(root,map));
}
private static boolean traversal(Node root, HashMap<Integer, Integer> map) {
if(root==null)
{
return false;
}
if(map.containsKey(root.data))
{
//map contains the element already i.e there is a duplicate
return true;
}
// as root is not null and not already in map,add its data value to map
map.put(root.data,0);
//checking if duplicate is present in left OR right subtree
return traversal(root.left,map)||traversal(root.right,map);
}
}
class Node
{
// Node has data,pointer to left and right child
int data;
Node left,right;
Node(int value)
{
this.data=value;
}
}
Note:
- Time Complexity:O(n)
(In worst case,we will be traversing the whole tree and algorithm would take O(n) time as tree has n nodes) - Space Complexity:O(n)
(In worst case i.e when no duplicates are present we will be storing all the nodes data value in the Map and would require O(n) space as tree has a total of n nodes)
