Tree's Pre-Order, In-Order and Post-Order Traverse Summary

To traverse a tree, there r three basic ways: preorder, inorder and postorder. All the three methods can be implemented in recursion or non-recursion. Here to simplify the problem, we assume that the tree is a binary tree.

Recursion Traversal

It is easy to recursively traverse a tree.

1.Preorder: root->left->right

public traverse(TreeNode root){

    visit(root);

    traverse(root.left);

    traverse(root.right);

}

2.Postorder: left->right->root

public traverse(TreeNode root){

    traverse(root.left);

    traverse(root.right);

    visit(root);

}

3.Inorder traverse: left->root->right

public traverse(TreeNode root){

    traverse(root.left);

    visit(root);

    traverse(root.right);

}

Non-recursion Traversal

When implementing traversal using the non-recursive method, we might need some extra space (stack) to store some tree nodes. Morris Inorder Traversal presents a method to traverse a binary tree using O(1) space and O(n) time.

1.Preorder: root->left->right

Considering stack is the first-in-last-out Container, we should push the right node into stack before the left node so that the left node can be popped and visited earlier. //pop root, push right, push left

public traverse(TreeNode root){

    if(root==null) return ;

    Stack<TreeNode> stack = new Stack<>();

    stack.push(root);

    while(!stack.isEmpty()){

        TreeNode node = stack.pop();   //visit the node

        if(node.right!=null) stack.push(node.right);

        if(node.left!=null) stack.push(node.left);

    }

}

2.Postorder: left->right->root

Postorder is similar the preorder, but "first pop the root, then push the left, then push the right". So the visiting is like "root, right, left". In the end, reverse the sequence, we can get "left, right, root".

public traverse(TreeNode root){

    if(root==null) return ;

    Stack<TreeNode> stack = new Stack<>();

    List<TreeNode> list = new ArrayList<>();

    stack.push(root);

    while(!stack.isEmpty()){

        TreeNode node = stack.pop();

        list.add(node);

        if(node.left!=null) stack.push(node.left);     

        if(node.right!=null) stack.push(node.right);  

    }

    for(int i = list.size()-1;i>=0;i--){

        visit(list.get(i));

    }

}

3.Inorder traverse: left->root->right

public traverse(TreeNode root){

    if(root==null) return ;

    Stack<TreeNode> stack = new Stack<>();

    List<TreeNode> list = new ArrayList<>();

    TreeNode cur = root;

    while(true){

        if(root.left!=null){

            stack.push(root);

            cur = cur.left;

        }else{

            if(stack.isEmpty()){

                break;

            }else{

                TreeNode parent = stack.pop(); //visit the node now

                cur = parent.right;

            }

        }

    }

}

Morris Inorder Traverse

public traverse(TreeNode root){

    if(root==null) return ;

    TreeNode cur = root;

    while(cur!=null){

        if(cur.left==null){    //visit the right node next;

             visit(cur);

             cur = cur.right;

        }else{

             TreeNode predecessor = cur.left;

             //find the Predecessor of the cur node.

             while(predecessor.right!=null && predecessor.right!=cur) predecessor = predecessor.right;

             if(predecessor.right==null){

                 //have not visited cur node's left tree, build the blue link in the graph

                 predecessor.right = cur;

                 cur = cur.left;

             }else{

                 //have visited cur node's left tree, remove the blue link in the graph

                 predecessor.right = null;

                 visit(cur);

                 cur = cur.right;

             }

        }

    }

}