3
\$\begingroup\$

I want you to give me some feedback on how I could make it better or simpler.

public class NonRecursiveTraversal {

    private TreeNode root;

    private static class TreeNode {
        TreeNode left;
        TreeNode right;
        int item;

        TreeNode (TreeNode left, TreeNode right, int item) {
            this.left = left;
            this.right = right;
            this.item = item;
        }
    }

    public void createBinaryTree (Integer[] arr) {
        if (arr == null)  {
            throw new NullPointerException("The input array is null.");
        }

        root = new TreeNode(null, null, arr[0]);

        final Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        final int half = arr.length / 2;

        for (int i = 0; i < half; i++) {
            if (arr[i] != null) {
                final TreeNode current = queue.poll();
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

                if (arr[left] != null) {
                    current.left = new TreeNode(null, null, arr[left]);
                    queue.add(current.left);
                }
                if (right < arr.length && arr[right] != null) {
                    current.right = new TreeNode(null, null, arr[right]);
                    queue.add(current.right);
                }
            }
        }
    }

    public void preOrder() {   
        if (root == null) return;

        final Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.add(root);        

        while (!stack.empty()) {
            TreeNode node = stack.pop();           
            System.out.print(node.item + " ");
            // LIFO
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
    }

    public void reverseOrder() {   
        if (root == null) return;

        final Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.add(root);        

        while (!stack.empty()) {
            TreeNode node = stack.pop();           
            System.out.print(node.item + " ");
            // LIFO
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
    }

    public void inOrder() {
        if (root == null) return;

        final Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;

        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.add(node);
                node = node.left;
            } else {
               node = stack.pop();
               System.out.print(node.item + " "); 
               node = node.right; 
            }
        }
    }


    public void postOrder  () {
        if (root == null) return;

        final Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;

        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                if (node.right != null) stack.add(node.right);
                stack.add(node);
                node = node.left;
            }

            node = stack.pop();

            // (node.right) != null means this node is parent of that tiny subtree
            // stack.pop != null ensures it was not the root.
            if (node.right != null && !stack.isEmpty() && node.right == stack.peek()) {
                TreeNode nodeRight = stack.pop();
                stack.push(node);
                node = nodeRight;
            } else {
                System.out.print(node.item + " ");
                node = null;
            }
        }
    }
}

Also, please correct my complexities: time and space both being \$O(n)\$.

\$\endgroup\$
1
\$\begingroup\$

I would not throw NullPointerException; it indicate that you are trying to use a variable which is null. Throw IllegalArgumentException instead; it indicated that arguments provided are not in a legal state.

And I personally don't like nesting too much loops and conditions. Try to separate them into smaller methods. When you put a block of code into a method, you are documenting it with the method name. Same applies for long conditions.

For example,

node.right != null && !stack.isEmpty() && node.right == stack.peek()

takes a while to "decipher". When you put it into the method isParentOfSubtree(...), it is obvious.

Also consider using some logger instead of System.out.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.