Home

Binary Tree Inorder Traversal

A old tree 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

Patreon Become a Patron Coffee icon Buy me a coffee