All the Tree Traversal you need (not recursively!) Too

I got this idea of going through Leetcode again to learn Python in a more fun way. The first thing is basic data structures, and we definitely cannot forget binary tree.

Here are all the tree traversal solutions. All solutions are accepted on Leetcode. I only include the recursive version for the preorder traversal, since all others are similar and trivial.

If you need the Java version, see here.

Enjoy. :)


Preorder

The recursive way has two versions, the first one uses two functions while the second one use a nested recursive function inside the global one. See here for my post about the nested function in Python.

def preOrder(root):
    """
    iterative version
    :param root:
    :return:
    """
    rst = []
    if not root:
        return rst
    stack = [root]
    while stack:
        curr = stack.pop()
        if curr.right is not None:
            stack.append(curr.right)
        if curr.left is not None:
            stack.append(curr.left)
        rst.append(curr.val)
    return rst

def preOrderRec(root):
    """
    recursive version
    :param root:
    :return:
    """
    rst = []
    preorderHelper(root, rst)
    return rst

def preorderHelper(root, rst):
    if root is not None:
        rst.append(root.val)
        preorderHelper(root.left, rst)
        preorderHelper(root.right, rst)


def preOrderRec2(root):
    """
    nested inner recursive function
    :param root:
    :return:
    """
    rst = []

    def recursion(root):
        if root:
            rst.append(root.val)
            recursion(root.left)
            recursion(root.right)
    recursion(root)
    return rst

Inorder:

def inOrder(root):
    """
    in order traversal, iterative
    use a stack
    :param root:
    :return:
    """
    rst = []
    if not root:
        return rst
    stack = []
    while root or stack:
        if root:
            stack.append(root)
            root = root.left
        else:
            root = stack.pop()
            rst.append(root.val)
            root = root.right
    return rst

Postorder:
This one is quite different from the Java version. Since Python does not have any peek() method for the list class, I cannot use the way I used in the Java version (Actually, there is a way: use a deque, popleft() first and then appendleft(), but I don't think it's quite efficient).
In Python, I used two stacks. Basically, it looks like this:

1. append the root to the first stack
2. pop the root out the first stack and append it to the second stack
3. append the left child followed by the right child of the root (if any exists)
4. repeat 2 and 3 until the first stack is empty
5. pop the nodes in the second stack and append it to the result list

Below the Python version is the Java version using the conventional method, you can compare the two method. :)

def postOrder(root):
    """
    iterative way, using two stacks
    :param root:
    :return:
    """
    rst = []
    if not root:
        return rst
    stack1 = [root]
    stack2 = []
    while stack1:
        curr = stack1.pop()
        if curr.left is not None:
            stack1.append(curr.left)
        if curr.right is not None:
            stack1.append(curr.right)
        stack2.append(curr)
    while stack2:
        rst.append(stack2.pop().val)
    return rst

Java version:

public ArrayList postorderTraversal(TreeNode root) {
        ArrayList rst = new ArrayList();
        if (root == null)
            return rst;
        Stack stack = new Stack();
        TreeNode curr = null;
        TreeNode prev = null;
        stack.push(root);
        while (!stack.empty())
        {
            curr = stack.peek();
            //prev == null, root
            //traverse down
            if (prev == null || prev.left == curr || prev.right == curr)
            {
                if (curr.left != null)
                    stack.push(curr.left);
                //need to traverse to the bottom of the tree first before goes to the right side
                else if (curr.right != null)
                    stack.push(curr.right);
            }
            // here comes the right side
            else if (curr.left == prev)
            {
                if (curr.right != null)
                    stack.push(curr.right);
            }
            //finally we can add nodes
            else
            {
                rst.add(curr.val);
                stack.pop();
            }
            prev = curr;
        }
        return rst;
    }

Level order:

from collections import deque

def levelOrder(root):
    """
    level order traversal
    :param root:
    :return:
    """
    rst = []
    if not root:
        return rst
    q = deque([root])
    while q:
        size = len(q)
        level = []
        for i in range(size):
            curr = q.popleft()
            if curr.left is not None:
                q.append(curr.left)
            if curr.right is not None:
                q.append(curr.right)
            level.append(curr.val)
        rst.append(level)
    return rst

Zigzag level order:

def zigzag(root):
    rst = []
    if not root:
        return rst
    thisLevel = [root]
    reverse = True
    while thisLevel:
        nextLevel = []
        level = []
        while thisLevel:
            curr = thisLevel.pop()
            level.append(curr.val)
            if reverse:
                if curr.left is not None:
                    nextLevel.append(curr.left)
                if curr.right is not None:
                    nextLevel.append(curr.right)
            else:
                if curr.right is not None:
                    nextLevel.append(curr.right)
                if curr.left is not None:
                    nextLevel.append(curr.left)

        thisLevel = nextLevel
        reverse = not reverse
        rst.append(level)
    return rst