How to convert a binary tree into a binary decision diagram

Question

struct TreeNode {
    int num;
    TreeNode* left;
    TreeNode* right;
};

TreeNode* cons_tree(int num, TreeNode *l, TreeNode *r) {
    TreeNode* tmp;
    tmp = new TreeNode;
    tmp->val = num;
    tmp->left = l;
    tmp->right = r;
    return tmp;
}

TreeNode* ordered_insertion_tree(int num, TreeNode *t) {
    if(t == NULL) {
        return cons_tree(num, NULL, NULL);
    }
    else if(num < t->val) {
        t->left = ordered_insertion_tree(num, t->left);
        return t;
    }
    else {
        t->right = ordered_insertion_tree(num, t->right);
        return t;
    }
}

Binary Decision Diagram (BDD)

Binary Search Tree (BST)

The code above shows how to create a BST. But, I would like my program to act like a truth table shown in the BDD image.

Differences between the 2 diagrams:

1. The dotted lines in the BDD image represent a "0" and the filled line represents a "1" in user input.
2. For the BST, when the user input is less than the root node it represents the left tree.
3. Root node for BDD is a string "x1" and for BST is an int 8.

For example, if the user inputs the string "000", "011", "110" and "111", these leaf nodes will have the string "1".

***The input will be appended into a vector of strings named values. So, values[0] represents "000" and so on. ***

My questions are:

1. How should I rewrite the ordered_insertion_tree function? Initially I was using int which allows me to compare values but now it has changed to std::string and I can't figure out how to make the comparisons.
2. How do I change the values of the nodes? From "x1", representing the first integer, to "x2" ... "xn" for n number of integers and finally to 0/1 representing the truth table.

Thank you for reading!