Ok, code reviewers, I want you to pick my code apart and give me some feedback on how I could make it better or more simple. Also its really hard to make this code work if preorder array contains duplicate. Any code/psuedocode is useful.
public class PreOrderTraversalBST {
private TreeNode root;
private static class TreeNode {
TreeNode left;
int item;
TreeNode right;
TreeNode (TreeNode left, int item, TreeNode right) {
this.left = left;
this.item = item;
this.right = right;
}
}
/**
* QQ: is there any alternative for this ?
*/
private static class Counter {
int counter;
Counter(int counter) {
this.counter = counter;
}
}
public void preOrderRecursive (int[] a) {
root = dpPreOrderRecursive (a, new Counter(0), Integer.MIN_VALUE, Integer.MAX_VALUE );
}
private TreeNode dpPreOrderRecursive (int[] arr, Counter counter, int min, int max) {
if (counter.counter < arr.length && arr[counter.counter] > min && arr[counter.counter] < max) {
int item = arr[counter.counter];
TreeNode treeNode = new TreeNode(null, item, null);
counter.counter++;
treeNode.left = dpPreOrderRecursive(arr, counter, min, item);
treeNode.right = dpPreOrderRecursive(arr, counter, item, max);
return treeNode;
}
return null;
}
public void preOrderWithStack (int[] arr) {
final Stack<TreeNode> stack = new Stack<TreeNode>();
root = new TreeNode(null, arr[0], null);
stack.push(root);
int i = 1;
while (arr[i] < root.item) {
TreeNode node = new TreeNode(null, arr[i], null);
if (arr[i] < stack.peek().item) {
stack.peek().left = node;
} else {
TreeNode temp = null;
while (!stack.isEmpty() && arr[i] >= stack.peek().item) {
temp = stack.pop();
}
temp.right = node;
stack.push(temp);
}
stack.push(node);
i++;
}
TreeNode rightNode = new TreeNode(null, arr[i], null);
root.right = rightNode;
stack.push(rightNode);
i++;
while (i < arr.length) {
TreeNode node = new TreeNode(null, arr[i], null);
if (arr[i] >= stack.peek().item) {
stack.peek().right = node;
stack.push(node);
} else {
TreeNode temp = null;
while (!stack.isEmpty() && arr[i] < stack.peek().item) {
temp = stack.pop();
}
temp.left = node;
stack.push(temp);
}
stack.push(node);
i++;
}
}
}
Complexity check. Does stack based solution account to O(nlogn) time comlexity or O(n2) ?
