CareerCup

Use Morris Traversal. The idea is -

1. Initialize root as current
2. while current is not NULL
	a) if current has no left child
		- print current and set current = current.right
	b) else 
		- set current as rightmost node of left child

Source Code:

void inorderWithConstantSpace(TreeNode *root) {
	if(!root) return root;	
	TreeNode *current = root;
	while(current) {
		if(current->left) {
			TreeNode *leftChild = current->left;
			TreeNode *tmp = leftChild;
			TreeNode *rightMost;
			while(leftChild) {
				rightMost = leftChild;
				leftChild = leftChild->right;
			}
			rightMost->right = current;
			current->left = nullptr;
			current = tmp;
		} else {
			printf("%d ", current->value);
			current = current->right;
		}
	}
}

I had this question a long time ago, and managed to pseudo-solve it. But now thinking about how to code it, I can't even imagine how it could possibly work.

static void printInorder(Node root) {
                while (root != null) {
                        while (root.left != null) {
                                Node p = root;
                                while (p.left.left != null) {
                                        p = p.left;
                                }
                                print(p.left.value);
                                p.left = p.left.right;
                        }
                        print(root.value);
                        root = root.right;
                }
        }

In order traverse the tree, for each node visit, swap the node data with the minimum node data in the tree. To find minimum, we need to have another tree traversal.
Since extra space is not allowed, we are not able to use hash table to indicate which nodes are swapped (containing min in the right position), we need to slightly modify the node structure to have a flag indicating whether the data is "swappable" or not.
At the end of the process, the tree becomes a BST and takes O(n^2) time complexity.

However, any in order traversals (recursive or non-recursive) take O(n) space which violate the requirement. Therefore, I think the question is asking O(1) space for temporary data storage.

Can we use heapify concept of Min heap & then print Min element ?? correct me if i'm wrong ?

O(1) space would be possible traversing the tree N times and marking the selected nodes.

Flagging notes is actually taking O(n) space since you'd have to add extra data on each node.
By changing the node without taking extra space, you'd have to change the left/right pointers. (So that's another hint.)

If the tree is a complete binary tree. We can suggest a Heap solution.
Now talking about a general case where it may or may not be a complete BT:
1) Find the smallest element in the tree
2) Delete the smallest element you found & print the same
3) Rebalance the tree to ensure it still remains a BST.
Repeat steps 1 to 3 until you are done with all elements.
The algorithm is inefficient with O(n^2) time complexity but the desired O(1) space

Morris Traversal，here is the AC code of Leetcode #94

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode *pre = NULL, *cur = root;
        vector<int> res;
        while (cur != NULL) {
            if (cur->left == NULL) {
                res.push_back(cur->val);
                cur = cur->right;
            } else {
                pre = cur->left;
                while (pre->right && pre->right != cur) {
                    pre = pre->right;
                }
                if (pre->right == NULL) {
                    pre->right = cur;
                    cur = cur->left;
                } else {
                    pre->right = NULL;
                    res.push_back(cur->val);
                    cur = cur->right;
                } 
            }
        }
        return res;
    }
};

Basicly every method that uses a stack or recursion is not O(1) in space. So if you can modify the tree, you just need to make a simple node rotation so in the end your tree will look just like a list. Code should be something like this:

def inorder_O1_Space(s):
        current = s
        while current != None:
                if current.left != None:
                        # rearrange the tree
                        child = current.left
                        current.left = child.right
                        child.right = current
                        current = child
                else:
                        print current.value
                        current = current.right

Morris algorithm can solve this problem. Is there any way to pre-order or post-order in O(1) space by Morris algorithm?

1. Write a function to delete a node like: void delete(Node n);
2. Write a function to find the most left node like: Node FindMostLeftNode(Node n);
3. Write a function to check the node is a leaf like: bool isLeaf(Node n);
4. Write a function to output the node like: void output(Node n);
5. Find the most left node, if the node is a leaf, remove it, if not, let the node=node.right ;

void InorderTraverse(Node root)
{
	Node mostLeft=FindMostLeftNode(root);
	while(mostLeft!=null)
	{
		output(mostLeft);
		if(isLeaf(mostLeft))
		{
			delete(mostLeft);
		}
		else
		{
			mostLeft=mostLeft.right;
		}
		
		mostLeft=FindMostLeftNode(root);
	}
}

1. Write a function to delete a node like: void delete(Node n);
2. Write a function to find the most left node like: Node FindMostLeftNode(Node n);
3. Write a function to check the node is a leaf like: bool isLeaf(Node n);
4. Write a function to output the node like: void output(Node n);
5. Find the most left node, if the node is a leaf, remove it, if not, let the node=node.right ;

void InorderTraverse(Node root)
{
	Node mostLeft=FindMostLeftNode(root);
	while(mostLeft!=null)
	{
		output(mostLeft);
		if(isLeaf(mostLeft))
		{
			delete(mostLeft);
		}
		else
		{
			mostLeft=mostLeft.right;
		}
		
		mostLeft=FindMostLeftNode(root);
	}
}

The idea is simple:
- starting from root check all nodes, if curr node has left child
	if has: move curr node as right child in most right node in left subtree
		   and use curr parent node as parent for left node
	if not: move current to right child
- print tree where every node has only right node

Note: root node can be changed, and eventually it will be the first node we have to print.

public static void printInOrder(Node root){
        if (root == null) return;
        boolean isReady = false;

        while (!isReady){
            isReady = true;
            Node curr = root;
            while(true){
                if (curr.L != null){
                    isReady = false;
                    curr.L.P = curr.P;
                    if (curr.P != null){
                        curr.P.R = curr.L;
                    } else {
                        root = curr.L;
                    }
                    Node mostRight = findMostRight(curr.L);
                    mostRight.R = curr;
                    curr.P = mostRight;
                    curr.L = null;
                } else {
                    curr = curr.R;
                    if (curr == null) break;
                }
            }
        }
        Node curr = root;
        while (curr != null){
            print(curr);
            curr = curr.R;
        }
    }

    private static void print(Node n) {
        System.out.printf("%s ", n.val);
    }

    private static Node findMostRight(Node root){
        Node curr = root;
        while (curr != null){
            if (curr.R == null) return curr;
            curr = curr.R;
        }
        return null;
    }

I think this is simple and straigh forward in-order traversal as shown bellow if O(1) is required without counting the call stack.

public static void InOrderTraversal(Node root)
{
	if(root == null)
		return;
	
	InOrderTraversal(root.Left);
	Console.WriteLine(root.Data);
	InOrderTraversal(root.Rigth);	
}

Now stating that the call stack counts towards the O(1). Here the best way is to flatten the three into a list where the Next is the Right. Adding the parent node to the right most of the left side.

Note:

Notice that in the code bellow keeps integrity of tree fixing the new Right of the previous node after performing the flatening and also return the new root element.

This is not necesary for the algorithm as I could easily don't care about the reference integrity of the tree during traversal so no need for caring about the prevParent nor returning the new root.

public static void InOrderTraversalO1(Node root)
{
	
	Node parent = root;
	Node newRoot = null;

	// Dummy node to not check for null
	Node prevParent = new Node();

	while(parent != null)
	{
		if(parent.Left == null)
		{
			Console.WriteLine(parent.Data);

			if(newRoot == null)
			{
				newRoot = parent;
			}

			prevParent = parent;
			parent = parent.Right;
		}
		else
		{
			Node left = parent.Left;
			Node rightMost = left;

			// Find right most
			while(rightMost .Rigth != null)
			{
				rightMost = rightMost .Right;	
			}

			
			rightMost.Right = parent;
			parent.Left = null;

			parent = left;

			// Keep integrity 
			prevParent.Right = parent;
		}
	}
	
	return newParent;
}

After thinking more about my own question ;-P, I think there's this one solution that seems that it might work, though I'd have to test it:
Step 1: Keep rotating the tree clockwise until there's no left
Step 2: Output root, move root to root right
Step 3: Repeat step 1.

There are some details about the question though (and this is just what I kinda remember from the original interview question, feel free to just interpret the problem as it is written).
#1 - call-stacks do count as space, so recursion is out of the picture for O(1) space.
#2 - I'm pretty sure the solution had to be O(n) time as well.
#3 - This part I can't remember for sure, but I thought we had to restore the tree in its original state after the traversal (in which case my solution here wouldn't even work). Now I could be wrong about this.)

Here is the solution

Current <= Root;
while(Current is not null)
    if Current -> left is not null
         Current = Current -> Left;
    else
         Print Current.Value
         Current.Printed = true;
         If Current -> Right is not null
             Current = Current -> Right;
         else
              Current = Current -> Parent;

Can we just use Heapify concept of Min Heap to modify the tree and then output Min value from the tree ??