Leetcode: Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree

   1
    \
     2
    /
   3

return [1,2,3].

Solution 1:

We want to implement this algorithm using constant extra space,  i.e.,  we cannot use recursion or a stack to keep the parent node.

Modifying the original tree
Creating threaded links to the next node to be processed and as the tree can be modified, there is not need to remove them.

We show an example of the algorithm in the next figure, where the dotted lines show the false links used to traverse the tree.

public class Solution {

    public ArrayList<Integer> preorderTraversal(TreeNode root) {

        ArrayList<Integer> solution = new ArrayList<Integer>();

        TreeNode current, temp;

        current=root;

        while(current != null)

        {

            solution.add(current.val);

            if(current.left == null)

            {

                current = current.right;

            }

            else

            {

                temp = current.left;

                while(temp.right != null && temp.right != current)

                    temp=temp.right;

                if(temp.right == null)

                {

                    temp.right = current.right;

                    current = current.left;

                }

                else

                //temp == current (We already have processed the left tree)

                {

                    temp.right = null; //We remove the threading links

                    current = current.right;

                }

            }

        }

        return solution;

    }

}

Solution 2 Without modifying the original tree
In this case we have to use threaded trees (http://en.wikipedia.org/wiki/Threaded_binary_tree).

The links marked are removed after traversing the links.

public class Solution {

    public ArrayList<Integer> preorderTraversal(TreeNode root) {

        ArrayList<Integer> solution = new ArrayList<Integer>();

        TreeNode current, temp;

        current=root;

        while(current != null)

        {

            if(current.left == null)

            {

                solution.add(current.val);

                current = current.right;

            }

            else

            {

                temp = current.left;

                while(temp.right != null && temp.right != current)

                    temp=temp.right;

                if(temp.right == null)

                {

                    solution.add(current.val);

                    temp.right = current.right;

                    current = current.left;

                }

                else

                {

                    temp.right = null; //We remove the threading links

                    current = current.right;

                }

            }

        }

        return solution;

    }

}