# O(1) space with same time complex of Stack solution - Morris Traversal of Tree

• The Stack solution seems use O(h) space well the time complex of next() function is more than O(1).
I try to use Morris Tree Traversal to solve this issue which saves space. However the time complex of construction of the class BSTIterator is O(n) (instead of O(h) to building the Stack). Time complex of next() function keep the same, between O(1) and O(h), since we are always have to find the right child node's most left child.

``````/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

public class BSTIterator {

public BSTIterator(TreeNode root) {
TreeNode pre = null;
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
pre = cur.left;
while (pre.right != null && pre.right != cur) {
pre = pre.right;
}
if (pre.right == null) {
pre.right = cur;
cur = cur.left;
} else {
cur = cur.right;
}
} else {
cur = cur.right;
}
}
}

/** @return whether we have a next smallest number */
public boolean hasNext() {
}

/** @return the next smallest number */
public int next() {
if (nextNode != null) {
while (nextNode.left != null && nextNode.left.val > head.val) {
nextNode = nextNode.left;
}
}

return ret;
}
}

/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.