NUHMAN.com

Introduction

LeetCode 94: Binary Tree Inorder Traversal asks you to implement an inorder traversal of a binary tree. In an inorder traversal, the nodes are recursively visited in this order: left subtree → root → right subtree. The challenge requires you to implement both recursive and iterative solutions.

In this article, we’ll explore how to solve this problem using both approaches in Go and understand the time and space complexities associated with them.

Problem Statement

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

Example:

go

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

Explanation: For the binary tree:

markdown

    1
     \
      2
     /
    3

The inorder traversal is: [1, 3, 2].

Approach: Recursive vs Iterative

1. Recursive Approach:

The recursive approach is a straightforward solution to this problem. In an inorder traversal, we:

• First visit the left subtree.
• Then visit the current root node.
• Finally, visit the right subtree.

This method naturally fits into a recursive structure, where the traversal of each subtree is handled by recursive function calls.

2. Iterative Approach:

The iterative approach uses a stack to mimic the recursive function calls. We keep pushing nodes onto the stack until we reach the leftmost node. After that, we pop nodes from the stack, process them, and then visit the right subtree.

Go Implementation

1. Recursive Approach

go

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
    var result []int
    var helper func(*TreeNode)

    helper = func(node *TreeNode) {
        if node == nil {
            return
        }
        helper(node.Left)
        result = append(result, node.Val)
        helper(node.Right)
    }

    helper(root)
    return result
}

Explanation (Recursive Approach):

1. Helper Function:
2. We define a recursive helper function that takes a node as an argument. If the node is nil, we return immediately (base case).
3. Inorder Traversal:

• Recursively visit the left subtree (helper(node.Left)).
• Add the current node’s value to the result slice.
• Recursively visit the right subtree (helper(node.Right)).

1. Final Output:
2. The result slice is returned after the traversal is complete.

2. Iterative Approach

go

func inorderTraversal(root *TreeNode) []int {
    var result []int
    var stack []*TreeNode
    current := root

    for current != nil || len(stack) > 0 {
        // Reach the leftmost node
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }

        // Pop the node from the stack and visit it
        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, current.Val)

        // Move to the right subtree
        current = current.Right
    }

    return result
}

Explanation (Iterative Approach):

1. Use a Stack:
2. We use a stack to simulate the recursive calls. The idea is to keep pushing nodes onto the stack until we reach the leftmost node.
3. Traverse Left Subtree:
4. The first for loop continues pushing nodes onto the stack until we reach a nil left node.
5. Visit Node:
6. Once we reach the leftmost node, we pop the top node from the stack, add its value to the result, and then set current to the right child of the popped node to continue the traversal.
7. Continue Traversal:
8. We repeat this process until we have processed all nodes (i.e., when the stack is empty and current is nil).

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(n)

Where:

• Time Complexity: In both the recursive and iterative approaches, each node is visited exactly once, leading to a time complexity of O(n), where n is the number of nodes in the tree.
• Space Complexity:
• In the recursive approach, the space complexity is O(h), where h is the height of the tree, as the recursion depth corresponds to the height of the tree. In the worst case (a skewed tree), the space complexity is O(n).
• In the iterative approach, we use a stack to store nodes. In the worst case, the space complexity is also O(n) if the tree is skewed (all nodes are on one side).

Edge Cases

1. Empty Tree:

• Input: root = nil
• Output: []
• Explanation: An empty tree results in an empty traversal.

1. Single Node Tree:

• Input: root = [1]
• Output: [1]
• Explanation: A tree with just one node will return that single node as the result.

1. Skewed Tree (All Nodes Have Only Right or Left Children):

• Input: root = [1, null, 2, null, 3]
• Output: [1, 2, 3]
• Explanation: In a right-skewed tree, the traversal would visit nodes in order from left to right.

1. Balanced Tree:

• Input: root = [2, 1, 3]
• Output: [1, 2, 3]
• Explanation: For a balanced tree, the nodes will be visited in sorted order.

Conclusion

LeetCode 94: Binary Tree Inorder Traversal is a foundational problem for understanding tree traversal algorithms. In this article, we explored both the recursive and iterative solutions to solve this problem using Go.

• The recursive approach offers a clear and simple implementation with a natural mapping to the definition of inorder traversal.
• The iterative approach is slightly more complex but avoids the overhead of recursion and is a good exercise in simulating recursive behavior using a stack.

Both approaches have O(n) time complexity, where n is the number of nodes in the tree, and O(n) space complexity in the worst case for a skewed tree.