Binary trees are one of the most fundamental data structures in computer science. They serve as the basis for various real-world applications like databases and network routing algorithms. One of the standard operations on binary trees is the inorder traversal. In this article, we will deep dive into the Binary Tree Inorder Traversal problem on LeetCode and discuss various Pythonic approaches to solving this problem.
Table of Contents
- Understanding the Problem Statement
- Introduction to Binary Trees
- Recursive Approach
- Iterative Approach Using Stack
- Morris Traversal
- Time and Space Complexity Analysis
Understanding the Problem Statement
The problem on LeetCode is titled “Binary Tree Inorder Traversal” and has the following description:
Given the root of a binary tree, return the inorder traversal of its nodes’ values.
Input: root = [1, null, 2, 3] Output: [1, 3, 2]
In inorder traversal, the tree is traversed in the following order: left subtree -> root -> right subtree.
Introduction to Binary Trees
A binary tree is a tree data structure where each node has at most two children referred to as the left child and the right child. For algorithms on binary trees, a common basic step is tree traversal, i.e., processing each node in the tree exactly once.
One of the most intuitive solutions for inorder traversal is using recursion. In this approach, we have a helper function that accepts a node as a parameter. If the node is not null, the function recursively calls itself for the left child, processes the current node, and then recursively calls itself for the right child.
Here’s what the Python code looks like:
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: TreeNode): def helper(node, result): if node: helper(node.left, result) result.append(node.val) helper(node.right, result) result =  helper(root, result) return result
Iterative Approach Using Stack
The recursive approach uses the function call stack. We can also simulate the inorder traversal iteratively using our own stack. This involves using a while loop that continues until the stack is empty or the current node is null.
Python code for this approach:
class Solution: def inorderTraversal(self, root: TreeNode): result, stack = ,  current = root while current or stack: # Reach the leftmost node while current: stack.append(current) current = current.left # Process the top of the stack current = stack.pop() result.append(current.val) # Move to the right subtree current = current.right return result
The Morris Traversal is an interesting approach that doesn’t use recursion or a stack, making it more space-efficient. It’s based on threaded binary trees and involves modifying the tree while traversing and then changing it back to its original form.
Here’s the Python code for Morris Traversal:
class Solution: def inorderTraversal(self, root: TreeNode): result =  current = root while current: if not current.left: result.append(current.val) current = current.right else: # Find the inorder predecessor pre = current.left while pre.right: pre = pre.right # Make current the right child of the inorder predecessor pre.right = current temp = current # Store current node current = current.left # Move current to its left temp.left = None # Avoid infinite loops return result
Time and Space Complexity Analysis
- Recursive Approach: Time complexity is O(n), where n is the number of nodes, and space complexity is O(h), where h is the height of the tree due to the function call stack.
- Iterative Approach Using Stack: Time complexity is O(n), and space complexity is O(h) due to the stack.
- Morris Traversal: Time complexity is O(n), but the space complexity is O(1) since it doesn’t use additional data structures for the traversal.
In this article, we explored the Binary Tree Inorder Traversal problem on LeetCode and discussed three different approaches in Python: recursive, iterative with a stack, and Morris Traversal. The Morris Traversal is particularly interesting due to its constant space complexity. However, it is worth noting that this method modifies the tree during the traversal, and it’s essential to understand the implications of this before using it in certain applications. The recursive and iterative approaches are more straightforward and generally more widely used. Understanding these traversal techniques is fundamental to solving more complex problems on binary trees.