# Binary Tree Inorder Traversal

• The Morris traversal method is truly amazing !! very creative approach

• Data Structure is amazing!

• That's not Morris traversal, since that doesn't destroy the tree (which yours does).

• @ManuelP Thank you for your advice. Actually, I do not destroy the tree, I construct the tree just want to understand easier. but you are right, it is not an official way to explain this way

• The example answer should be [4,2,5,1,3,6]..... The animation is wrong also.

• @monkeykingyan You do destroy the tree. When you're done, it's not the same as it was in the beginning. It's very different.

And btw it's not space complexity O(1). Because your ArrayList uses linear extra space (both extra capacity at all times, and duplicate space whenever it grows its capacity and copies its elements).

• @flgt Yes, the example should be as same as the 3rd one, I will contact LeetCode to change it, thank you for letting me know

• @ManuelP Yes, thank you for letting me know, Space Complexity should be O(n).

• science technichian

• C++ solution
Using a variable to determine whether to go left or right

``````class Solution {
public:
vector<int> inorderTraversal(TreeNode* root)
{
vector<int> vals;
if (!root)
return vals;
stack<TreeNode*> stk;
stk.push(root);
bool goRight = false;

while (!stk.empty())
{
TreeNode *tmp = stk.top();
if (goRight)
{
vals.push_back(tmp->val);
stk.pop();
if (tmp->right)
{
stk.push(tmp->right);
goRight = false;
}
}
else
{
if (tmp->left)
{
stk.push(tmp->left);
}
else
{
goRight = true;
}
}
}
return vals;
}
};
``````

• I guess I was closer to the first answer.

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
return helper(root, new ArrayList<Integer>());

``````}
private List<Integer> helper(TreeNode root, List<Integer> list) {
if (root == null) {
return list;
}
list = helper(root.left, list);
list = helper(root.right, list);
return list;
}
``````

}

:/

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list =new ArrayList<>();
inorder(root, list);
return list;
}
public void inorder(TreeNode root,List<Integer> list) {
if(root == null) return;
inorder(root.left, list);
inorder(root.right, list);
}
}

• did the thread tree break down the last part of the tree 3->6 to a separate subtree of 6->3?

• the tree is modified through the traversal, it can be reverted back to its original shape after the completion.
Check this link: https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

• Morris traversal should be O(1) extra space. You cant count the solution set as extra space since that was what was asked in the first place.
The whole point of Morris traversal is to eliminate the need for extra space(either call stack or stack in interative method).
No point of doing all that extra work of modifying all the nodes for no gain in time or space complexity.

• class Solution(object):

``````def rec(self, root, res):
if(root == None):
return

self.rec(root.left, res)
res.append(root.val)
self.rec(root.right, res)

def inorderTraversal(self, root):
res = []
self.rec(root, res)
return res``````

• ``````public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) return res;
List<Integer> resl = inorderTraversal(root.left);
List<Integer> resr = inorderTraversal(root.right);