Removing duplicates from array using Binary Search Tree

Problem : given an array e.g. [3,5,4,2,1,2,3,1]

Need : filter the array such as to remove duplicates ( reference : http://www.careercup.com/question?id=3515013)

Approach: There are many ways to do this

a.) sort the array and compare elements in sequential fashion and remove duplicates : Complexity – O(nlogn)

b.) create a hash and based on hash function put values in hash only once, if you encounter duplicates, ignore them : Complexity – O(n)

c.) another approach is to do it with using Binary Search Tree, pick one element at a time, search if it exists in tree, if not, create node, set pointers and if you encounter duplicates, just ignore them by not creating tree nodes: Complexity – O(n)

I tried doing this using Java, took a long time to get it right, but finally it worked. The program also prints the three traversal techniques that we can run on a tree – PreOrder, PostOrder and InOrder

Please note that in code, left=true means ” left child” and left=false means “right child”.

Program is as follows:

BSTNode.java

     /*
     * To change this template, choose Tools | Templates
     * and open the template in the editor.
     */

    package careercup.google;

    /**
     *
     * @author Harit
     */
    public class BSTNode {
        private int value;
        private int leftChild;
        private int rightChild;

        public BSTNode(int v){
            value = v;
            leftChild = -1;
            rightChild = -1;
        }

        public int getValue(){
            return this.value;
        }

        public int getChild(boolean left){
            if(left){
                return this.leftChild;
            }
            else{
                return this.rightChild;
            }
        }
        public void setChild(int child, boolean left){
            if(left){
                this.leftChild = child;
            }else{
                this.rightChild = child;
            }
        }
    }

RemDupArrayBST.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package careercup.google;

import java.util.ArrayList;

/**
 *
 * @author Harit
 */
public class RemDupArrayBST {
    /* Output Array of Nodes */
    private static ArrayList<BSTNode> nodes = new ArrayList<BSTNode>();
    private static int parent = -1;
    private static boolean left = false;

    public static void main(String args[]){
        /* Sample Input Array */
        //int[] input_array = new int[]{3,1,2,1};
        int[] input_array = new int[]{3,5,4,2,1,2,3,1};
        //int[] input_array = new int[]{1,2,3,2,4,4};
        /* end sample input */

        for(int i=0; i<input_array.length; i++){
            if(nodes.size() == 0){
                /* tree is empty, add root */
                BSTNode node = new BSTNode(input_array[i]);
                nodes.add(node);
            }else{
                /* search if node already exists */
                if(!contains(input_array[i])){
                    BSTNode node = new BSTNode(input_array[i]);
                    nodes.add(node);
                    nodes.get(parent).setChild(nodes.size()-1, left);
                }else{
                    System.out.println(input_array[i] + " : already exists - ignoring");
                }
            }
        }

        /* final print */
        System.out.print("Inorder Traversal: ");
        inOrderTraverse(nodes.get(0));

        System.out.println("");

        System.out.print("PostOrder Traversal: ");
        postOrderTraverse(nodes.get(0));

        System.out.println("");

        System.out.print("PreOrder Traversal: ");
        preOrderTraverse(nodes.get(0));

        System.out.println("");
    }

    private static boolean contains(int value){
        int index = 0;
        while(index >= 0){
            if (nodes.get(index).getValue() == value){
                return true;
            }
            if (nodes.get(index).getValue() > value){
                parent = index;
                left = true;
                index = nodes.get(index).getChild(true);
            }else{
                parent = index;
                left = false;
                index = nodes.get(index).getChild(false);
            }
        }
        return false;
    }

    private static void inOrderTraverse(BSTNode node){
        if(node == null){
            return;
        }
        if(node.getChild(true) != -1){
            inOrderTraverse(nodes.get(node.getChild(true)));
        }
        System.out.print(node.getValue() + " ");
        if(node.getChild(false) != -1){
            inOrderTraverse(nodes.get(node.getChild(false)));
        }
    }

    private static void postOrderTraverse(BSTNode node){
        if(node == null){
            return;
        }
        if(node.getChild(true) != -1){
            postOrderTraverse(nodes.get(node.getChild(true)));
        }
        if(node.getChild(false) != -1){
            postOrderTraverse(nodes.get(node.getChild(false)));
        }
        System.out.print(node.getValue() + " ");
    }

    private static void preOrderTraverse(BSTNode node){
        if(node == null){
            return;
        }
        System.out.print(node.getValue() + " ");
        if(node.getChild(true) != -1){
            preOrderTraverse(nodes.get(node.getChild(true)));
        }
        if(node.getChild(false) != -1){
            preOrderTraverse(nodes.get(node.getChild(false)));
        }
    }
}

Output:

2 : already exists – ignoring

3 : already exists – ignoring

1 : already exists – ignoring

Inorder Traversal: 1 2 3 4 5

PostOrder Traversal: 1 2 4 5 3

PreOrder Traversal: 3 2 1 5 4