Binary Tree Inorder Traversal

Photo by Chris Leipelt

This post is part of the Algorithms Problem Solving series.

Problem description

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

Examples

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [2,1]

Example 5:

Input: root = [1,null,2]
Output: [1,2]

Solutions

The first step is to make sure we have a initial list to add elements and return as the result of our implementation. We can do this by initializing the list in when the class instance is created:

def __init__(self):
        self.inorder_list = []

Then we need to verify if the tree exists or it is an "empty tree" (basically the empty tree here is a None value).

if root:
        # The tree has nodes, do the traversal!

To do an inorder traversal, we need to just go to the leftmost node, add the node value, and then go to the right node. We can do this recursively:

class Tree:
    def __init__(self):
        self.inorder_list = []

    def inorder_traversal(self, root):
        if root:
            self.inorder_traversal(root.left)
            self.inorder_list.append(root.val)
            self.inorder_traversal(root.right)

        return self.inorder_list

With recursion, the algorithm looks pretty simple.

The time and space complexities are both O(n).

Resources

• Learning Python: From Zero to Hero
• Algorithms Problem Solving Series
• Stack Data Structure
• Queue Data Structure
• Linked List
• Tree Data Structure

Have fun, keep learning, and always keep coding!

My Twitter and Github