Hash map

[lost110]

Hello! How would I implement this program without using the library "<unordered_map>" . Is there any alternate. I know how to make a hash table though. Thanks



#include <iostream>
#include <unordered_map>
using namespace std;

// Data structure to store a Binary Tree node
struct Node
{
int data;
Node *left, *right;

Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};

// Recursive function to do a pre-order traversal of the tree and
// fill the map with diagonal sum of elements
void diagonalSum(Node* root, int diagonal, auto &map)
{
// base case: empty tree
if (root == nullptr)
return;

// update the current diagonal with node's value
map[diagonal] += root->data;

// recur for left subtree by increasing diagonal by 1
diagonalSum(root->left, diagonal + 1, map);

// recur for right subtree with same diagonal
diagonalSum(root->right, diagonal, map);
}

// Function to print the diagonal sum of given binary tree
void diagonalSum(Node* root)
{
// create an empty map to store diagonal sum for every slope
unordered_map<int, int> map;

// do pre-order traversal of the tree and fill the map
diagonalSum(root, 0, map);

// traverse the map and print diagonal sum
for (int i = 0; i < map.size(); i++) {
cout << map[i] << " ";
}
}

int main()
{
Node* root = nullptr;

/* Construct below tree
1
/ \
/ \
2 3
/ / \
/ / \
4 5 6
/ \
/ \
7 8
*/

root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
root->right->right = new Node(6);
root->right->left->left = new Node(7);
root->right->left->right = new Node(8);

diagonalSum(root);

return 0;
}

[lost110]

Also the key word "auto" is not allowed in my course!

[jonnin]

any random access container can do hashing. vectors and arrays being the most common choices. But, I do not see any point: you appear to store a bunch of numbers and then print them in a loop, iterating them. Where are you needing the hash table key/value lookups? I do not see what you are doing that cannot be done with a vector push-back, in other words.

[dhayden]

A the name implies, unordered_map stores items in no particular order. This is in conflict with the following code in your program which assumes that the items DO have an order:

// traverse the map and print diagonal sum
for (int i = 0; i < map.size(); i++) {
    cout << map[i] << " ";
}

So you want to print them out by key from lowest key to highest. You could do this with a regular std::map<int,int>, or with a std::vector<int>. If using a vector, you'll have to ensure that he vector is big enough before inserting the item:

if (map.size() <= diagonal) {
    map.resize(diagonal+1);
}
map[diagonal] += root->data;