Preorder, Inorder and Postorder 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

They can all be done via recursion

White Boards

Pre-Order

In-Order

Post-Order

Code

Pre-Order

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

class Solution:
    def _pre(self, root, res):

        if root:
            res.append(root.val)
            self._pre(root.left, res)
            self._pre(root.right, res)
        return res


    def preorderTraversal(self, root):

        res = []
        if root is None:
            return res

        return self._pre(root, res)

In-Order

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

class Solution:
    def _inorder(self, root, res):
        if root:
            self._inorder(root.left, res)
            res.append(root.val)
            self._inorder(root.right, res)
        return res

    def inorderTraversal(self, root):

        res = []
        if root is None:
            return res

        return self._inorder(root, res)

Post-Order

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

class Solution:
    def postorderTraversal(self, root):

        res = []
        if root is None:
            return res

        return self._post(root, res)

    def _post(self, root, res):
        if root:
            self._post(root.left, res)
            self._post(root.right, res)
            res.append(root.val)

        return res