Question

Create a subclass of BinaryTree whose nodes have fields for storing preorder, post-order, and in-order numbers. Write methods preOrderNumber(), inOrderNumber(), and postOrderNumbers() that assign these numbers correctly. These methods should each run in O(n) time.

Answer 1

To create a subclass of BinaryTree with preOrderNum, inOrderNum, and postOrderNum fields in nodes, one must write preOrderNumber(), inOrderNumber(), and postOrderNumbers() methods. These methods traverse the tree and assign numbers to nodes based on the traversal order, which is done with O(n) time complexity, with n being the number of nodes.

Step-by-step explanation:

private int preNum = 0;
public void preOrderNumber(Node node) {
if (node == null) return;
node.preOrderNum = ++preNum;
preOrderNumber(node.left);
preOrderNumber(node.right);
}

private int inNum = 0;
public void inOrderNumber(Node node) {
if (node == null) return;
inOrderNumber(node.left);
node.inOrderNum = ++inNum;
inOrderNumber(node.right);
}

private int postNum = 0;
public void postOrderNumber(Node node) {
if (node == null) return;
postOrderNumber(node.left);
postOrderNumber(node.right);
node.postOrderNum = ++postNum;
}