Java easy iterative O(n) space and time solution

  • 1

    This is just a standard iterative inorder traversal of BST. O(n) space for the worst case instead of O(logn) for a skewed tree where all the nodes go to the stack.

     public class Solution {
            public void recoverTree(TreeNode root) {
                if (root == null) {
                TreeNode first, second, prev;
                first = second = prev = null;//initialized to null to check if has been assigned value before
                Stack<TreeNode> stack = new Stack<>();
                pushLeft(stack, root);
                while (!stack.isEmpty()) {
                    root = stack.pop();//root is current node
                    pushLeft(stack, root.right);
                    if (prev != null && prev.val > root.val) {
                        if (first == null) {
                            first = prev;//first gets updated for the first time only
                        second = root;// second gets updated every time prev>root
                    prev = root;
                int tmp = first.val;
                first.val = second.val;
                second.val = tmp;
            private void pushLeft(Stack<TreeNode> stack, TreeNode root) {
                while (root != null) {
                    root = root.left;

Log in to reply

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