Binary Tree Inorder Traversal - Python Solution

1. Introduction

Inorder traversal of a binary tree is a fundamental concept in tree-based algorithms, where one visits the nodes of a binary tree in a specific order - left subtree, root, right subtree. This problem is a classic example to understand tree traversal techniques in computer science and is often used to test the understanding of binary tree concepts in coding interviews.

Problem

Given the root of a binary tree, the task is to return the inorder traversal of its nodes' values. Inorder traversal involves visiting the left subtree first, then the root node, and finally the right subtree.

2. Solution Steps

1. Create a function to traverse the tree.

2. Traverse the left subtree recursively.

3. Process the current node (add its value to the result).

4. Traverse the right subtree recursively.

5. Combine the results from these traversals to form the inorder traversal of the tree.

3. Code Program

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorderTraversal(root):
    def inorder(node):
        if not node:
            return []
        # Traverse left subtree, process current node, then right subtree
        return inorder(node.left) + [node.val] + inorder(node.right)

    return inorder(root)

# Example Usage
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
print(inorderTraversal(root))

Output:

[1, 3, 2]

Explanation:

1. Recursive Function: The inorder function is defined to perform the traversal. It visits nodes recursively.

2. Left Subtree: It first calls itself to traverse the left subtree.

3. Current Node: After traversing the left subtree, it processes the current node (adds its value to the traversal result).

4. Right Subtree: It then calls itself to traverse the right subtree.

5. Traversal Order: The order of these operations ensures that the nodes are visited in the inorder sequence.

6. Overall Result: The function returns the complete inorder traversal of the binary tree.