All of the solutions (e.g. [this](http://https://leetcode.com/problems/binary-tree-inorder-traversal/solution/)) say that Morris Traversal has O(1) space complexity.\nIs it really true?\n\nYes, we don\'t use additional collections, but we change the given tree. We add new links to it, and the links count is equal to the stack size of the casual depth-first approach.\n\nSo, in the worst case, we will add N new links (space complexity O(n)):\n```\n        5\n       / \n      4   \n     / \n    3\n   /\n  2\t\n /\n1\n```\n\nAnd for balanced trees, we will add logn links (space complexity O(logn)).\n\nWhy do links in the external collection matter but are inserted in-place not?

All of the solutions (e.g. this) say that Morris Traversal has O(1) space complexity.\nIs it really true?\n\nYes, we don\'t use additional collections, but we c