Leetcode – Binary Tree Inorder Traversal in Python

Spread the love

Introduction

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

  1. Introduction
  2. Understanding the Problem Statement
  3. Introduction to Binary Trees
  4. Recursive Approach
  5. Iterative Approach Using Stack
  6. Morris Traversal
  7. Time and Space Complexity Analysis
  8. Conclusion

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.

For example:

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.

Recursive Approach

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

Morris Traversal

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

  1. 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.
  2. Iterative Approach Using Stack: Time complexity is O(n), and space complexity is O(h) due to the stack.
  3. 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.

Conclusion

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.

Leave a Reply