Question

Consider binary search trees with 7 nodes. In this problem you will need to re-implement the (pseudo) code implementation of the binary, AVL, and AA trees and produced the (pseudo) code to answer the following questions: Preliminaries Come up with a hash function that turns a BST into a string. When one tree differs from another only in the values of the keys but not in the structure they should hash to the same value. Trees with different structure should never hash to the same value. (Hint: in order traversal is your friend) Vanilla BST This is a binary tree with the only restriction that it has the BST property

Answer 1

A hash function for a BST can be created using an in-order traversal, where each null node is represented by a special character and nodes are separated, ensuring distinctive representation for different structures.

Step-by-step explanation:

The student's question pertains to the construction of a hash function that represents the structure of a binary search tree (BST) independently of the nodes' values. To create a string representation for any BST that fulfills these requirements, you can use an in-order traversal, which visits the left subtree, the root node, and then the right subtree recursively. When a null node is encountered, a special character (such as an asterisk) should be added to the string, ensuring that each unique tree structure maps to a distinct string.

Here's an example of pseudo code:

function bstToString(node):
if node is null:
return "*"
else:
return bstToString(node.left) + "." + bstToString(node.right)

The "." serves as a separator between the left and right sub-trees, and the "*" denotes a null node, preventing different structures from hashing to the same string.