Generally, tree traversal can be specified as inorder traversal (only for binary tree) , preorder traversal, postorder traversal and level order traversal. Level order traversal can be easily implemented with a queue. But other three traversals could be implemented recursively, iteratively with O(n) space and even iteratively with O(1) space.

We focus on binary tree first.

The easiest way of binary tree’s inorder traversal, preorder traversal, postorder traversal is the recursive way. In fact, it is the definition of them.

//Inorder
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    
    public void helper(TreeNode root, List<Integer> res)
    {
        if(root != null)
        {
            helper(root.left, res);
            res.add(root.val);
            helper(root.right, res);
        }
    } 
}

//Preorder
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> res;
    public List<Integer> preorderTraversal(TreeNode root) {
        res = new ArrayList<>();
        if(root == null) return res;
        helper(root);
        return res;
    }
    public void helper(TreeNode root)
    {
        if(root != null)
        {
            res.add(root.val);
            helper(root.left);
            helper(root.right);
        }
    }
}

//Postorder
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    
    public void helper(TreeNode root, List<Integer> res)
    {
        if(root != null)
        {
            helper(root.left, res);
            helper(root.right, res);
            res.add(root.val);
        }
    }
}

Then I’d like to talk about how to implement them iteratively. Using the stack is a direct idea. We could always push the left child to the stack and when the node is popped, the node’s left subtree has been visited. And then the node’s right subtree is solved as the same way.

For the inorder traversal, we should visit the node after its left subtree. So the node should be visited after it is popped.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> s = new ArrayDeque<>();
        TreeNode p=root;
        while(s.size() > 0 || p != null)
        {
            if(p != null)
            {
                s.push(p);
                p = p.left;
            }
            else
            {
                p = s.pop();
                res.add(p.val);
                p = p.right;
            }
        }
        return res;
    }
}

And for preorder traversal, we should visit the node before its left subtree. So the node should be visited before it is pushed.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Deque<TreeNode> s = new ArrayDeque<>();
        List<Integer> res=new ArrayList<>();
        while(s.size()>0||root!=null)
        {
            if(root==null)
            {
                root=s.pop();
                root=root.right;
            }
            else
            {
                res.add(root.val);
                s.push(root);
                root=root.left;
            }
        }
        return res;
    }
}

For the postorder tree, there are two ways of implementing it.

The first way is easy to understand. We can implement preorder traversal from right. The normal preorder traversal is that we should first visit the root then visit the left subtree and visit the right subtree finally. But now we should first visit the root then visit the right subtree and visit the left subtree finally. When we complete this traversal, we should reverse the result and output it. Then we get the postorder traversal result.

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<Integer>();
        Stack<TreeNode> s = new Stack<>();
        while(s.size() > 0 || root != null)
        {
            if(root == null)
            {
                root = s.pop();
                root = root.left;
            }
            else
            {
                res.addFirst(root.val);
                s.push(root);
                root = root.right;
            }
        }
        return res;
    }
}

However, there is a limit of this method. We have to complete the whole traversal to get the results. That means we could not make the postorder traversal an iterator.

So let’s focus on the second way. We can attach a boolean variable to each node to show if it is visited. In the postorder traversal we should visit the node after its left subtree and right subtree. So when we pop it at the first time, it should not be output as postorder traversal now. So if it is not visited, set it visited and push it back to the stack. Then visit its right subtree. When the right subtree is solved, the node should be popped again. Now its boolean variable shows it has been visited. We could output it.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    class NodeContainer{
        TreeNode node;
        boolean visited;
        NodeContainer(TreeNode n, boolean flag)
        {
            node = n;
            visited = flag;
        }
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<NodeContainer> s = new ArrayDeque<>();
        while(s.size() > 0 || root != null)
        {
            if(root != null)
            {
                s.push(new NodeContainer(root, false));
                root = root.left;   
            }
            else
            {
                NodeContainer nc = s.pop();
                root = nc.node;
                if(!nc.visited)
                {
                    nc.visited = true;
                    s.push(nc);
                    root = root.right;
                }
                else
                {
                    res.add(root.val);
                    root = null;// Set root to null in order to pop the stack in the next step
                }
            }
        }
        return res;
    }
}

Now we will discuss the optimal method of the three binary tree traversal. It just need O(1) space. It is called Morris Traversal.

The difficulty of implementing it with O(1) space is that we have to return to the root when we visit its subtree. So we should find a way to record the root when visiting the subtree. In Morris Traversal, the idea is when we get a root, we should find the rightmost node in its left subtree. And set the rightmost node’s right child as the current root. Then when we completing visiting the left subtree, we could get the root back with the right child.

For inorder subtree, we should output the node after visiting its left subtree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode cur = root, prev = null;
        while(cur != null)
        {
            if(cur.left == null)
            {
                res.add(cur.val);
                cur = cur.right;
            }
            else
            {
                prev = cur.left;
                while(prev.right != null && prev.right != cur)
                {
                    prev = prev.right;
                }
                if(prev.right == null)
                {
                    prev.right = cur;
                    cur = cur.left;
                }
                else
                {
                    prev.right = null;
                    res.add(cur.val);
                    cur = cur.right;
                }
            }
        }
        return res;
    }
}

For preorder traversal, we should output the node before visiting its left subtree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode cur = root, prev = null;
        while(cur != null)
        {
            if(cur.left == null)
            {
                res.add(cur.val);
                cur = cur.right;
            }
            else
            {
                prev = cur.left;
                while(prev.right != null && prev.right != cur)
                {
                    prev = prev.right;
                }
                if(prev.right == null)
                {
                    prev.right = cur;
                    res.add(cur.val);
                    cur = cur.left;
                }
                else
                {
                    prev.right = null;
                    cur = cur.right;
                }
            }
        }
        return res;
    }
}

For postorder traversal, when we get back the node, we must reversely output the nodes in the path from the current node’s left child to its left subtree’s rightmost child. It guarantees the right subtree is visited before the root.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        TreeNode dump = new TreeNode(0);
        dump.left = root;
        List<Integer> res = new ArrayList<>();
        TreeNode cur = dump, prev = null;
        while(cur != null)
        {
            if(cur.left == null)
            {
                cur = cur.right;
            }
            else
            {
                prev = cur.left;
                while(prev.right != null && prev.right != cur)
                {
                    prev = prev.right;
                }
                if(prev.right == null)
                {
                    prev.right = cur;
                    cur = cur.left;
                }
                else
                {
                    printReverse(cur.left, prev, res);
                    prev.right = null;
                    cur = cur.right;
                }
            }
        }
        return res;
    }
    
    private void printReverse(TreeNode start, TreeNode end, List<Integer> res)
    {
        List<Integer> temp = new ArrayList<>();
        while(start != end.right)
        {
            temp.add(start.val);
            start = start.right;
        }
        Collections.reverse(temp);
        for(int i : temp) res.add(i);
    }
}

Although the O(1) space method is trivial, we can just remember the main idea, set the left subtree’s rightmost node’s right child to the current root. Then we could implement it based on this.

The binary tree’s level order traversal is very easy. We don’t discuss much in this article.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> resi;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        TreeNode tmp;
        int qs;
        while(true)
        {
            qs = q.size();
            resi = new ArrayList<>();
            for(int i = 0; i < qs; i++)
            {
                tmp = q.poll();
                if(tmp != null)
                {
                    resi.add(tmp.val);
                    q.offer(tmp.left);
                    q.offer(tmp.right);
                }
            }
            if(q.size() == 0) break;
            res.add(resi);
        }
        return res;
    }
}

We have discussed binary tree. Then for N-ary tree, it only has preorder traversal, postorder traversal and level order traversal. First, the recursive way of the preorder traversal and the postorder traversal is the following.

//Preorder
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    public void helper(Node root, List<Integer> res)
    {
        if(root != null)
        {
            res.add(root.val);
            if(root.children != null)
            {
                for(int i = 0; i < root.children.size(); i++)
                {
                    helper(root.children.get(i), res);
                }
            }
        }
    }
}

//Postorder
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    public void helper(Node root, List<Integer> res)
    {
        if(root != null)
        {
            if(root.children != null)
            {
                for(int i = 0; i < root.children.size(); i++)
                {
                    helper(root.children.get(i), res);
                }
            }
            res.add(root.val);
        }      
    }
}

Then we can implement them iteratively with one stack.

For preorder traversal, for each root we could push its child from right to left. It can guarantee we can pop the node from the left child to the right.

//Iterative with one stack
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        Deque<Node> s = new ArrayDeque<>();
        s.push(root);
        while(s.size() > 0)
        {
            root = s.pop();
            res.add(root.val);
            if(root.children != null)
            {
                for(int i = root.children.size() - 1; i >= 0; i--)
                {
                    s.push(root.children.get(i));
                }
            }
        }
        return res;
    }
}

For postorder traversal, we could use the reverse way.

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<Integer> postorder(Node root) {
        LinkedList<Integer> res = new LinkedList<Integer>();
        Deque<Node> s = new ArrayDeque<>();
        if(root == null) return res;
        s.push(root);
        while(s.size() > 0)
        {
            root = s.pop();
            res.addFirst(root.val);
            if(root.children != null)
            {
                for(int i = 0; i < root.children.size(); i++)
                {
                    s.push(root.children.get(i));
                }
            }
        }
        return res;     
    }
}

In this article, non-reverse postorder traversal and O(1) space traversal for N-ary tree will not be discussed because they are too complex.

And N-ary tree’s level order traversal is also easy.

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<Node> q = new LinkedList<>();
        if(root == null) return res;
        q.add(root);
        int qsize;
        Node tempnode;
        List<Integer> templist;
        while(q.size() > 0)
        {
            qsize = q.size();
            templist = new ArrayList<>();
            for(int i = 0; i < qsize; i++)
            {
                tempnode = q.poll();
                templist.add(tempnode.val);
                if(tempnode.children != null)
                {
                    for(int j = 0; j < tempnode.children.size(); j++)
                    {
                        q.add(tempnode.children.get(j));
                    }
                }
            }
            res.add(templist);
        }
        return res;
    }
}

Reference

[1] http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html

Leave a Reply

Your email address will not be published. Required fields are marked *