PLEASE PROVIDE INLINE COMMENTS FOR THE CODE BELOW SO I CAN UNDERSTAND. Original Question was: Design an algorithm for the following operations for a binary tree BT, and show the worst-case running times for each implementation: preorderNext(x): return the node visited after node x in a pre-order traversal of BT. postorderNext(x): return the node visited after node x in a post-order traversal of BT. inorderNext(x): return the node visited after node x in an in-order traversal of BT. class Node { public Node parent, left, right; int data; public Node(int data) { this.data = data; } public String toString() { return "" + this.data; } } public class BinaryTree { Node root; BinaryTree() { root = null; } public static Node preorderNext(Node v){ if(v.left != null) { return v.left; } if(v.right != null) { return v.right; } Node k = v.parent; while (k != null && (k.right == null || k.right.equals(v))) { v = k; k = k.parent; } if(k == null) { return null; } return k.right; } public static Node postorderNext(Node v){ Node k = v.parent; if(k == null) { return null; } if (k.right != null && k.right.equals(v)) { return k; } if(k.right == null) { return k; } k = k.right; while (k.left != null || k.right != null) { if(k.left != null) { k = k.left; } else { k = k.right; } } return k; } public static Node inorderNext(Node v) { if(v.right != null) { Node k = v.right; while (k.left != null) { k = k.left; } return k; } if(v.parent == null) { return null; } Node k = v.parent; if(k.left != null && k.left.equals(v)) { return k; } while (k != null && (k.right == null || k.right.equals(v))) { v = k; k = k.parent; } return k; } public static void main(String[] args) { Node[] n = new Node[9]; for (int i = 1; i <= 9; i++) { n[i-1] = new Node(i); } n[0].left = n[1]; n[0].right = n[2]; n[1].left = n[3]; n[1].right = n[4]; n[3].right = n[8]; n[2].left = n[5]; n[5].left = n[6]; n[6].right = n[7]; for(int i=1; i<=9; i++){ System.out.print("inOrderNext("+i+") = " + BinaryTree.inorderNext(n[i - 1]) + "\t"); System.out.print("preOrderNext("+i+") = " + BinaryTree.preorderNext(n[i - 1]) + "\t"); System.out.print("postOrderNext("+i+") = " + BinaryTree.postorderNext(n[i - 1]) + " "); } } }

The complexity for this approach is O(N)