How to make a random Expression Binary Tree

Question

I need to code a program that buildl a Binary Tree with two types of Node:
ConstNode: represent random numbers
OperaNode; represent operators [+, -, *, /]
I realized that:
+Each node has zero, one or two children
+Only OperaNode can have children
+All leaf node must be ConstNode
(Check the attached image for more details)
I can only build a Binary Tree with all random numeric elements. I don't know how to generate a random expression tree based on the code I had.

public class RandomBinaryTree {
private Random random = new Random();
public TreeNode binaryTreeGenerator(int n, int key){
if (n == 0)
return null;

TreeNode root = new TreeNode(key);

// Number of nodes in the left subtree (in [0, n-1])
int leftN = random.nextInt(n);

// Recursively build each subtree
root.setLeft(binaryTreeGenerator(leftN, key));
root.setRight(binaryTreeGenerator(n - leftN - 1, key));

return root;
}
}
I appreciate your help in solving this problem.

Answer 1

Expression: 3*(6-4)
(*)
/ \
(3) (-)
/ \
(6) (4)

Answer 2

To generate a random expression tree based on the given information, you can modify your binaryTreeGenerator function as follows:

public TreeNode binaryTreeGenerator(int n) {
if (n == 0) {
// If the number of nodes is 0, return null
return null;
}

if (n == 1) {
// If the number of nodes is 1, create a ConstNode and return it
int value = random.nextInt(100);
return new ConstNode(value);
}

// Otherwise, create an OperaNode
int operatorIndex = random.nextInt(4);
char operator = "+-*/"[operatorIndex];
OperaNode root = new OperaNode(operator);

// Generate the left subtree
int leftN = random.nextInt(n - 1);
root.setLeft(binaryTreeGenerator(leftN));

// Generate the right subtree
int rightN = n - leftN - 1;
root.setRight(binaryTreeGenerator(rightN));

return root;
}

In this modified function, the binaryTreeGenerator function first checks if the number of nodes n is 0 or 1. If n is 0, it returns null; if n is 1, it creates a ConstNode and returns it.

If n is greater than 1, the function creates an OperaNode with a randomly chosen operator (+, -, *, or /). It then generates the left and right subtrees using the binaryTreeGenerator function recursively, with the number of nodes in the left subtree being a random number between 0 and n-1, and the number of nodes in the right subtree being n - leftN - 1.

I hope this helps! Let me know if you have any other questions.