Please review the code for code cleanup, smart optimizations and best practices. Also verify my complexity: \$O(n^2)\$, where \$n\$ is the number of nodes.
/**
* This class traverses the tree and returns in-order representation.
* This class does not recursion and does not use stack.
* This code is threadsafe.
*/
public final class TraversalWithoutRecursionWithoutStack<T> {
private TreeNode<T> root;
/**
* Constructs a binary tree in order of elements in an array.
* The input list is treated as BFS representation of the list.
* Note that it is the clients reponsibility to not modify input list in objects lifetime.
*
* http://codereview.stackexchange.com/questions/31334/least-common-ancestor-for-binary-search-tree/31394?noredirect=1#comment51044_31394
*/
public TraversalWithoutRecursionWithoutStack(List<T> items) {
create(items);
}
/**
* Idea of inner class is supported by linked list and another code found here:
* http://stackoverflow.com/questions/5262308/how-do-implement-a-breadth-first-traversal
*
* @author SERVICE-NOW\ameya.patil
*/
private static class TreeNode<T> {
TreeNode<T> left;
T item;
TreeNode<T> right;
TreeNode(TreeNode<T> left, T item, TreeNode<T> right) {
this.left = left;
this.item = item;
this.right = right;
}
}
private void create (List<T> items) {
root = new TreeNode<T>(null, items.get(0), null);
final Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();
queue.add(root);
final int half = items.size() / 2;
for (int i = 0; i < half; i++) {
if (items.get(i) != null) {
final TreeNode<T> current = queue.poll();
final int left = 2 * i + 1;
final int right = 2 * i + 2;
if (items.get(left) != null) {
current.left = new TreeNode<T>(null, items.get(left), null);
queue.add(current.left);
}
if (right < items.size() && items.get(right) != null) {
current.right = new TreeNode<T>(null, items.get(right), null);
queue.add(current.right);
}
}
}
}
private TreeNode<T> getInorderSuccessor(TreeNode<T> node) {
assert node != null;
TreeNode<T> inorderSuccessorCandidate = node.left;
while (inorderSuccessorCandidate.right != null && inorderSuccessorCandidate.right != node) {
inorderSuccessorCandidate = inorderSuccessorCandidate.right;
}
return inorderSuccessorCandidate;
}
/**
* Returns the list containing items in inorder form.
*
* @returns the list of items in inorder.
*/
public List<T> inorderTraversal () {
final List<T> nodes = new ArrayList<T>();
TreeNode<T> node = root;
while (node != null) {
if (node.left == null) {
nodes.add(node.item);
node = node.right;
continue;
}
final TreeNode<T> inorderSuccessor = getInorderSuccessor(node);
if (inorderSuccessor.right == null) {
inorderSuccessor.right = node;
node = node.left;
} else {
inorderSuccessor.right = null;
nodes.add(node.item);
node = node.right;
}
}
return nodes;
}
public static void main(String[] args) {
/**
* 1
* 2 3
* 4 n n 7
*/
Integer[] arr1 = {1, 2, 3, 4, null, null, 7};
List<Integer> list1 = new ArrayList<Integer>();
for (Integer i : arr1) {
list1.add(i);
}
TraversalWithoutRecursionWithoutStack<Integer> traversalWithoutRecursionWithoutStack1 = new TraversalWithoutRecursionWithoutStack<Integer>(list1);
System.out.print("Expected: 4 2 1 3 7, Actual: ");
for (Integer i : traversalWithoutRecursionWithoutStack1.inorderTraversal()) {
System.out.print(i + " ");
}
System.out.println("\n--------------------------------");
/**
* 1
* 2 3
* 4 n 6 n
*/
Integer[] arr2 = {1, 2, 3, 4, null, 6};
List<Integer> list2 = new ArrayList<Integer>();
for (Integer i : arr2) {
list2.add(i);
}
TraversalWithoutRecursionWithoutStack<Integer> traversalWithoutRecursionWithoutStack2 = new TraversalWithoutRecursionWithoutStack<Integer>(list2);
System.out.print("Expected: 4 2 1 6 3, Actual: ");
for (Integer i : traversalWithoutRecursionWithoutStack2.inorderTraversal()) {
System.out.print(i + " ");
}
System.out.println("\n---------------------------------");
/**
* 1
* / \
* null 2
* / \ / \
* null null null 3
* / \ / \ / \ / \
* null null null null null null null 4
*
*/
Integer[] arr3 = {1, null, 2, null, null, null, 3, null, null, null, null, null, null, null, 4};
List<Integer> list3 = new ArrayList<Integer>();
for (Integer i : arr3) {
list3.add(i);
}
TraversalWithoutRecursionWithoutStack<Integer> traversalWithoutRecursionWithoutStack3 = new TraversalWithoutRecursionWithoutStack<Integer>(list3);
System.out.print("Expected: 1 2 3 4, Actual: ");
for (Integer i : traversalWithoutRecursionWithoutStack3.inorderTraversal()) {
System.out.print(i + " ");
}
System.out.println("\n---------------------------------");
/**
* 4
* / \
* 2 null
* / \ / \
* 1 null null null
*/
Integer[] arr4 = {4, 2, null, 1, null};
List<Integer> list4 = new ArrayList<Integer>();
for (Integer i : arr4) {
list4.add(i);
}
TraversalWithoutRecursionWithoutStack<Integer> traversalWithoutRecursionWithoutStack4 = new TraversalWithoutRecursionWithoutStack<Integer>(list4);
System.out.print("Expected: 1 2 4, Actual: ");
for (Integer i : traversalWithoutRecursionWithoutStack4.inorderTraversal()) {
System.out.print(i + " ");
}
}
}
inorderSuccessor.right = node;
duringinorderTraversal()
, making the data structure not a tree, feels like such a dirty hack, even if you undo it later. \$\endgroup\$