recalls that
Problem statement: Given a binary tree, implement a mid-order traversal and return an array containing its mid-order sequence.
For example given the following binary tree:
We recursively traverse the binary tree in the order of left, root, and right to get the following traversal:
The final result of the middle-order traversal can be output as: [3, 1, 9, 2, 4, 7, 5, 8, 6]
Morris trick
Morris mid-order traversal is a tree traversal algorithm designed to achieve O(1) space complexity without recursion or external data structures. The algorithm should efficiently access each node in a binary tree in mid-order sequence and print or process node values during traversal without the use of a stack or recursion.
The key idea is to create a temporary link between the current node and its rightmost node.
Let's first look at the middle-order traversal:
Discussion of practices
The mid-order predecessor of a node is the rightmost node in the left subtree. Therefore, when we traverse the left subtree, we will encounter a node with an empty right child, which is the last node in that subtree.Thus, we observe a pattern where whenever we are at the last node of a subtree, if the right child node points to null, we move to the parent node of that subtree。
When we are currently at a node, the following may occur:
Case 1: The current node has no left subtree
- Print the value of the current node
- Then to the right child of the current node
If there is no left subtree, we simply print the value of the current node, since there are no nodes on the left to traverse. After that, we move to the right child node to continue the traversal.
Case 2: There is a left subtree and the rightmost child of that left subtree points to null.
- Sets the rightmost child node of the left subtree to point to the current node.
- Moves to the left child of the current node.
In this case, we haven't visited the left subtree yet. We create a temporary link from the rightmost node of the left subtree to the current node.This link will help us later to determine when we have finished traversing the left subtree in order. After setting the link, we move to the left child node to explore the left subtree.
Case 3: A left subtree exists and the rightmost child of that left subtree already points to the current node.
- Print the value of the current node
- Restore temporary links (set them back to empty)
-
Move to the right child of the current node。
This situation is crucial to maintain the integrity of the tree structure. If the rightmost child node of the left subtree already points to the current node, it means that we have finished traversing the left subtree in order. We print the value of the current node and then restore the temporary links to restore the original tree structure. Finally, we move to the right child node to continue the traversal.
arithmetic
Step 1: Initialize current to traverse the tree. Set current to the root of the binary tree.
Step 2: When the current node is not empty: If the current node does not have a left child, print the value of the current node and move it to the right child, i.e., set the current node as its right child.
Step 3: The current node has a left child, we find the in-order predecessor of the current node. This in-order predecessor is the rightmost node of the left subtree.
- If the right child node of the in-order predecessor is empty:
- Sets the in-order predecessor right child node to the current node.
- Move to the left child of current
- If the right child of the in-order predecessor is not null:
- The right child of the in-order predecessor is set to null.
- Prints the value of the current node.
- Get current from the right child of the previous in-order predecessor and move to the right child of cuurent.
Repeat steps 2 and 3 until you reach the end of the tree.
code implementation
#include <iostream>
#include <sstream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <map>
using namespace std;
// TreeNode structure
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
// Function to perform iterative Morris
// inorder traversal of a binary tree
vector<int> getInorder(TreeNode* root) {
// Vector to store the
// inorder traversal result
vector<int> inorder;
// Pointer to the current node,
// starting from the root
TreeNode* cur = root;
// Loop until the current
// node is not NULL
while (cur != NULL) {
// If the current node's
// left child is NULL
if (cur->left == NULL) {
// Add the value of the current
// node to the inorder vector
inorder.push_back(cur->val);
// Move to the right child
cur = cur->right;
} else {
// If the left child is not NULL,
// find the predecessor (rightmost node
// in the left subtree)
TreeNode* prev = cur->left;
while (prev->right && prev->right != cur) {
prev = prev->right;
}
// If the predecessor's right child
// is NULL, establish a temporary link
// and move to the left child
if (prev->right == NULL) {
prev->right = cur;
cur = cur->left;
} else {
// If the predecessor's right child
// is already linked, remove the link,
// add current node to inorder vector,
// and move to the right child
prev->right = NULL;
inorder.push_back(cur->val);
cur = cur->right;
}
}
}
// Return the inorder
// traversal result
return inorder;
}
};
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->left->right->right = new TreeNode(6);
Solution sol;
vector<int> inorder = (root);
cout << "Binary Tree Morris Inorder Traversal: ";
for(int i = 0; i< (); i++){
cout << inorder[i] << " ";
}
cout << endl;
return 0;
}