Binary Tree Inorder Traversal

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

Have fun, keep learning, and always keep coding!