Mapping duplicate nodes from binary tree to a hashmap

Question

I'm trying to create a function that searches through a binary tree looking for duplicate nodes and stores the number of times each unique node appears in the tree into a hashmap.

Here's a more specific version of the question -

"Create a public class called YourBinaryTree that extends BinaryTree. Override protected Map<Object, Integer> valueCount() and have it return a Map mapping each object in the tree to the number of times that it appears. If the tree is empty (root is null) you should return an empty Map. Do not declare any fields in your class"

I'm tried recursively searching through the tree but I can't seem to get it to work because duplicate nodes are creating new mappings and not replace the values of old ones.

Here's the code I've written so far:

import java.util.Map;
import java.util.HashMap;

public class YourBinaryTree extends BinaryTree
{

protected Map<Object, Integer> valueCount()
{
    Map<Object, Integer> treeMap = new HashMap<>();
    
    if(root == null)
    {
        return treeMap;
    }
    
    if(root.left == null && root.right == null)
    {
        treeMap.put(root.value , 1);
        return treeMap;
    }
    
    return valueCount(root);
}

private Map<Object, Integer> valueCount(Node current)
{
    Map<Object, Integer> treeMap = new HashMap<>();
    
    if(current == null)
    {
        return treeMap;
    }
    
    if(treeMap.containsKey(current.value))
    {
        treeMap.put(current.value, treeMap.get(current) + 1);
    }
    else
    {
        treeMap.put(current.value, 1);
    }
    /*
    Map<Object, Integer> treeMapLeft = new HashMap<>();
    Map<Object, Integer> treeMapRight = new HashMap<>();
    
    treeMapLeft.putAll(valueCount(current.left));
    treeMapRight.putAll(valueCount(current.right));
    
    treeMapRight.forEach(
            (key, value)
            -> treeMapLeft.merge(key, value, (v1, v2) -> v1+v2));
        
    
    treeMap = treeMapLeft;
    */
    treeMap.putAll(valueCount(current.left));
    treeMap.putAll(valueCount(current.right));
    
    return treeMap;
}

}

Here's the code for the class that creates the Binary Tree:

public class BinaryTree
{
    protected class Node
    {
        protected Object value;
        protected Node left;
        protected Node right;
    
        Node(Object setValue)
        {
            value = setValue;
        }
    }
    protected Node root;
}

I've tried using the merge function but I'm really sure how to implement it. Any help would be very much appreciated, thank you! :)

score 2 · Answer 1 · edited Aug 08 '20 at 11:28

We just need to do a simple recursive tree traversal:

import java.util.Map;
import java.util.HashMap;

public class YourBinaryTree extends BinaryTree {
    private void traverse_tree(Node root, Map<Object, Integer> objectCountMap) {
        if(root == null) {
            return;
        }
        objectCountMap.putIfAbsent(root, 0);
        objectCountMap.put(root, objectCountMap.get(root) + 1);
        traverse_tree(root.left, objectCountMap);
        traverse_tree(root.right, objectCountMap);
    }

    public Map<Object, Integer> valueCount()
    {
        Map<Object, Integer> objectCountMap = new HashMap<>();
        traverse_tree(root, objectCountMap);
        return objectCountMap;
    }
}

Be careful that the class of the key of objectCountMap should implement equals() and hashcode() method properly.

According to equals() and hashcode() of Object class, 2 objects are equal only when their memory addresses are equal.
For example:

Object obj1 = new Object();
Object obj2 = new Object();
Map<Object, Integer> countMap = new HashMap<>();
countMap.put(obj1, 1);
countMap.put(obj2, 2);
countMap.get(obj1); // Returns 1
countMap.get(obj2); // Returns 2 

-----------

Object obj1 = new Object();
Object obj2 = obj1 // obj2 has same memory address as obj1
Map<Object, Integer> countMap = new HashMap<>();
countMap.put(obj1, 1);
countMap.put(obj2, 2);
countMap.get(obj1); // Returns 2
countMap.get(obj2); // Returns 2

score 0 · Answer 2 · answered Aug 08 '20 at 08:04

you are creating a new map in your valueCount method, which is empty, you need to pass your map object which is created in your overrided method in every call to value count method, to be updated. So your method wil look like this:

private void valueCount(Node current,HashMap<Object,Integer> treeMap){
     //rest of your code
}

Mapping duplicate nodes from binary tree to a hashmap

2 Answers2