Binary Tree Inorder Traversal - Leetcode Solution

Problem Statement:

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

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

Example 2: Input: root = [] Output: []

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

Approach:

The inorder traversal of a binary tree is to traverse the left sub-tree, then visit the root, and finally traverse the right sub-tree. As we know that it's a traverse of the tree, we can use Depth First Search (DFS) because it allows us to check the node in its left, right and current order, hence the inorder traversal's requirement.

Algorithm:

1. Define an empty list to store the inorder traversal.
2. Define a function, say inorder_helper, that takes a node as input and performs the inorder traversal on its left, current, and right node following the required order.
3. Check if the root node is not equal to Null, then perform the following steps: a) Call the inorder_helper function recursively for the left child node passing its reference. b) Append the current node's value to the list. c) Call the inorder_helper function recursively for the right child node passing its reference.
4. Finally, return the list of inorder traversal.

Pseudo Code:

function inorder(root):
    result = []                         // Initialize empty list
    inorder_helper(root, result)        // Call inorder_helper() and pass root and result list
    return result                       // return result list 

function inorder_helper(current_node, result_list):
    if current_node != null:
        inorder_helper(current_node.left, result_list)     // Recursive call for left child node
        result_list.append(current_node.val)               // Append current node's value to the list
        inorder_helper(current_node.right, result_list)    // Recursive call for right child node

Time Complexity:

Since we are visiting all the nodes of the tree, the time complexity of the algorithm is O(n), where n is the number of nodes in the binary tree.

Space Complexity:

For the auxiliary space, we are using a list to store the inorder traversal. The space occupied by the list is O(n), where n is the number of nodes in the binary tree.

Solution: Python implementation of the above algorithm:

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

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []             # Initialize empty list
        self.inorder_helper(root, result)       # Call inorder_helper() and pass root and result list
        return result           # return result list 
        
    def inorder_helper(self, current_node, result_list):
        if current_node is not None:
            self.inorder_helper(current_node.left, result_list)     # Recursive call for left child node
            result_list.append(current_node.val)                    # Append current node's value to the list
            self.inorder_helper(current_node.right, result_list)    # Recursive call for right child node

The above implementation passed all the test cases of the problem on LeetCode.

1