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
- 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!