Iterative Traversal for a Binary Tree

Problems

There are three ways to traverse a binary tree: preorder, inorder and postorder.

On Leetcode, there are three problems

144. Binary Tree Preorder Traversal

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

Input: [1,null,2,3] 1 \ 2 / 3

Output: [1,2,3]

94. Binary Tree Inorder Traversal

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

Input: [1,null,2,3] 1 \ 2 / 3

Output: [1,3,2]

145. Binary Tree Postorder Traversal

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

Input: [1,null,2,3] 1 \ 2 / 3

Output: [3,2,1]

Though Process

  • Use Stack
  • Stack is LIFO
  • Use stack to store the information of current node, right tree, left tree and action("execute" or "go-to")

White Boards

Pre-Order

Code

Pre-Order

Stack Order: right -> left -> node

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class StackCMD:
    def __init__(self, node, cmd):
        # cmd stores the current action
        # only two values "go-to" and "exec"
        # "go-to" go to a node, "exec" perform append node value to list
        self.node, self.cmd = node, cmd


class Solution:        

    def preorderTraversal(self, root):
        stack = []
        res = []
        # if none return an empty list
        if root is None:
            return res

        curr_node = root
        stack_cmd = StackCMD(curr_node, "go-to")
        stack.append(stack_cmd)

        while stack:
            curr_cmd = stack.pop()
            if curr_cmd.cmd == "exec":
                res.append(curr_cmd.node.val)
            else:
                assert(curr_cmd.cmd == "go-to")
                # make sure the cmd is either exec or go-to

                # stack is LIFO so append order: right->left->node
                # also check if right or left exists
                curr_node = curr_cmd.node
                if curr_node.right:
                    stack.append(StackCMD(curr_node.right, "go-to"))
                if curr_node.left:
                    stack.append(StackCMD(curr_node.left, "go-to"))
                stack.append(StackCMD(curr_node, "exec"))

        return res

In-Order

Stack Order: right -> node -> left

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class StackCMD:
    def __init__(self, node, cmd):
        # cmd stores the current action
        # only two values "go-to" and "exec"
        # "go-to" go to a node, "exec" perform append node value to list
        self.node, self.cmd = node, cmd


class Solution:        

    def inorderTraversal(self, root):
        stack = []
        res = []
        # if none return an empty list
        if root is None:
            return res

        curr_node = root
        stack_cmd = StackCMD(curr_node, "go-to")
        stack.append(stack_cmd)

        while stack:
            curr_cmd = stack.pop()
            if curr_cmd.cmd == "exec":
                res.append(curr_cmd.node.val)
            else:
                assert(curr_cmd.cmd == "go-to")
                # make sure the cmd is either exec or go-to

                # stack is LIFO so append order: right->node->left
                # also check if right or left exists
                curr_node = curr_cmd.node
                if curr_node.right:
                    stack.append(StackCMD(curr_node.right, "go-to"))
                stack.append(StackCMD(curr_node, "exec"))
                if curr_node.left:
                    stack.append(StackCMD(curr_node.left, "go-to"))

        return res

Post-Order

Stack Order: node -> right -> left

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class StackCMD:
    def __init__(self, node, cmd):
        # cmd stores the current action
        # only two values "go-to" and "exec"
        # "go-to" go to a node, "exec" perform append node value to list
        self.node, self.cmd = node, cmd


class Solution:        

    def postorderTraversal(self, root):
        stack = []
        res = []
        # if none return an empty list
        if root is None:
            return res

        curr_node = root
        stack_cmd = StackCMD(curr_node, "go-to")
        stack.append(stack_cmd)

        while stack:
            curr_cmd = stack.pop()
            if curr_cmd.cmd == "exec":
                res.append(curr_cmd.node.val)
            else:
                assert(curr_cmd.cmd == "go-to")
                # make sure the cmd is either exec or go-to

                # stack is LIFO so append order: node->right->left
                # also check if right or left exists
                curr_node = curr_cmd.node
                stack.append(StackCMD(curr_node, "exec"))
                if curr_node.right:
                    stack.append(StackCMD(curr_node.right, "go-to"))
                if curr_node.left:
                    stack.append(StackCMD(curr_node.left, "go-to"))

        return res