Binary Tree: Write a method void insert(const Entry &x) and the corresponding recursive function to insert an Entry x, passed as a parameter, into a linked binary tree. If the root is empty, the new entry should be inserted into the root, otherwise it should be inserted into the shorter of the two subtrees of the root (or into the left subtree if both subtrees have the same height). An empty tree is considered to have height 0 and a tree with only one node has height 1. You have to write all the methods and functions you need (e.g. you cannot use a height( ) function without writing it here).

template <class Entry>

class Binary_tree {

public:

void insert(const Entry &); // WRITE THIS METHOD

protected:

Binary_node *root;

};

template <class Entry>

struct Binary_node {

// data members:

Entry data;

Binary_node *left;

Binary_node *right;

// constructors:

Binary_node( );

Binary_node(const Entry &x);

};

void insert(const Entry &x) { // write this method