In-order Traversal of a Binary Tree Using Recursion : Leetcode Solution

Introduction

Binary tree traversal is a fundamental concept in computer science. One common traversal method is Inorder traversal, where the nodes are visited in the order: left subtree, root, and right subtree. This article explains a Python solution to perform an inorder traversal of a binary tree using recursion.

---

Problem Statement

Given the root of a binary tree, return its inorder traversal as a list of node values.

Example

Input:

    1
     \
      2
     /
    3

Output:

[1, 3, 2]

Explanation:

• First, visit the leftmost node: 1.

• Then, process the root: 3.

• Finally, traverse the right subtree: 2.

---

Approach

The solution uses recursion to traverse the tree in an inorder manner. Here's the step-by-step approach:

1. Base Case:

   • If the current node is None, return immediately.

2. Recursive Steps:

   • Traverse the left subtree by recursively calling the function on root.left.

   • Append the value of the current node to the result list.

   • Traverse the right subtree by recursively calling the function on root.right.

3. Driver Function:

   • Initialize an empty list result to store the traversal output.

   • Define a helper function inorder() that performs the recursion.

   • Call inorder(root) from the driver function and return the result list.

---

Complexity

• Time Complexity: $$O(n)$$

  • Each node is visited exactly once.

• Space Complexity: $$O(h)$$

  • The space required for the recursion stack depends on the height of the tree, where $$h$$ is the height of the tree.

---

Python Code

Here is the Python implementation of the solution:

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

class Solution(object):
    def inorderTraversal(self, root):
        result = []

        def inorder(root):
            if not root:
                return
            inorder(root.left)
            result.append(root.val)
            inorder(root.right)

        inorder(root)

        return result

---

Example Walk-through

Let’s walk through the algorithm with the input tree:

Input Tree:

    1
     \
      2
     /
    3

Steps:

1. Start at the root node 1. Call inorder(1).

2. Move to the left child of 1, which is None. Return immediately.

3. Add 1 to the result: [1].

4. Move to the right child of 1, which is 2. Call inorder(2).

5. Move to the left child of 2, which is 3. Call inorder(3).

6. Add 3 to the result: [1, 3].

7. Move to the right child of 3, which is None. Return immediately.

8. Add 2 to the result: [1, 3, 2].

Final Output:

[1, 3, 2]

---

Advantages of Recursion in Tree Traversals

1. Simplicity: The recursive approach is intuitive and mirrors the definition of tree traversal.

2. Minimal Code: Recursion avoids the need for complex loop structures, resulting in cleaner and more concise code.

---

Conclusion

In-order traversal is a core concept in tree algorithms. Using recursion makes the implementation straightforward and efficient. However, for large trees, consider iterative solutions to avoid stack overflow.

If you enjoyed this article, feel free to explore other traversal methods like pre-order and post-order traversals. Let’s keep learning together!

---

Let’s Connect! If you found this article helpful, feel free to connect with me on LinkedIn and check out more of my articles on Hashnode!