### Leetcode 94. Binary Tree Inorder Traversal

Inorder Traversal of a Binary Tree in C++

# Inorder Traversal of a Binary Tree in C++

## Introduction

In this blog post, we will discuss the implementation of an algorithm to perform an inorder traversal on a binary tree. The goal is to return the inorder traversal of its nodes' values. We will provide a step-by-step explanation of the code and discuss its complexity analysis. Additionally, we will explore the Morris Traversal method, which utilizes a threaded binary tree to optimize the traversal process. Let's dive into the details!

## Problem Statement

Given the root of a binary tree, we need to return the inorder traversal of its nodes' values. The inorder traversal visits the left subtree, then the current node, and finally the right subtree.

## Solution Overview

To perform an inorder traversal iteratively, we can use a modified version of Morris Traversal. The algorithm avoids using an explicit stack and instead modifies the tree structure itself to achieve the desired traversal order. The main idea is to establish a temporary link between the rightmost node of the left subtree and the current node. This link allows us to traverse the tree in a predefined order without losing the original right subtree.

## Solution Implementation

``````
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector inorderTraversal(TreeNode* root) {
vector res;
TreeNode* curr = root;
TreeNode* pre;
while (curr != nullptr) {
if (curr->left == nullptr) {
res.push_back(curr->val);
curr = curr->right; // move to the next right node
} else { // has a left subtree
pre = curr->left;
while (pre->right != nullptr) { // find the rightmost node in the left subtree
pre = pre->right;
}
pre->right = curr; // establish the temporary link
TreeNode* temp = curr; // store the current node
curr = curr->left; // move to the top of the new tree
temp->left = nullptr; // set the original left node to nullptr to avoid infinite loops
}
}
return res;
}
};
``````

The function `inorderTraversal` takes the root of the binary tree as input and returns a vector `res` containing the inorder traversal of the tree. We start with an empty result vector and initialize two pointers, `curr` and `pre`, to the root of the tree.

The algorithm uses a while loop to traverse the tree. Inside the loop, we check if the current node `curr` has a left subtree. If it doesn't, we push the value of `curr` to the result vector `res` and move `curr` to its right child using `curr = curr->right`. This step ensures that we traverse the right subtree after visiting the current node and its left subtree.

If `curr` has a left subtree, we need to establish a temporary link to the rightmost node of the left subtree. This link will allow us to return to the current node later. We initialize `pre` to the rightmost node of the left subtree by repeatedly moving `pre` to its right child until we reach the rightmost node.

After finding the rightmost node, we set `pre->right = curr` to establish the temporary link. We also store the current node in `temp` before moving `curr` to its left child. Setting `temp->left = nullptr` avoids infinite loops by disconnecting the original left subtree.

Finally, we return the result vector `res` containing the inorder traversal of the binary tree.

## Approach 3: Morris Traversal

In this method, we have to use a new data structure - Threaded Binary Tree, and the strategy is as follows:

1. Initialize the current node as the root.
2. While the current node is not NULL:
• If the current node does not have a left child, add its value to the result vector and move to the right child (`curr = curr->right`).
• If the current node has a left child:
• Find the rightmost node in the left subtree (the node with no right child). We will call this node `pre`.
• If `pre->right` is NULL, set `pre->right = curr` to establish the temporary link from `pre` to `curr`. This link indicates that we have visited the left subtree of `curr`.
• Move to the left child (`curr = curr->left`).
• If `pre->right` is not NULL, it means we have already visited the left subtree of `curr`. Remove the temporary link by setting `pre->right = NULL` and add the value of `curr` to the result vector.

The Morris Traversal method allows us to perform an inorder traversal without using an explicit stack. By utilizing the threaded binary tree concept, we establish temporary links that guide the traversal process.

## Complexity Analysis

The time complexity of the Morris Traversal algorithm is O(n), where n is the number of nodes in the binary tree. Each node is visited once, and establishing the temporary links takes constant time for each node.

The space complexity is O(1) since we do not require any additional data structures besides the output vector.

## Conclusion

In this blog post, we explored an iterative solution to perform an inorder traversal on a binary tree. The algorithm utilizes the Morris Traversal method, which modifies the tree structure itself to achieve the desired traversal order. We provided a step-by-step explanation of the code, discussed the complexity analysis, and introduced the threaded binary tree concept. The Morris Traversal method offers an efficient approach for inorder tree traversal without the need for an explicit stack.