Leetcode 94. Binary Tree Inorder Traversal
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 stepbystep 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:
 Initialize the current node as the root.

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, setpre>right = curr
to establish the temporary link frompre
tocurr
. This link indicates that we have visited the left subtree ofcurr
.  Move to the left child (
curr = curr>left
). 
If
pre>right
is not NULL, it means we have already visited the left subtree ofcurr
. Remove the temporary link by settingpre>right = NULL
and add the value ofcurr
to the result vector.
 Find the rightmost node in the left subtree (the node with no right child). We will call this node
 If the current node does not have a left child, add its value to the result vector and move to the right child (
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 stepbystep 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.
Comments
Post a Comment