Print nodes of two binary trees in ascending order

Question

Given two binary search trees, print the nodes in ascending order with time complexity O(n) and space complexity: O(1)

The trees cannot be modified. Only traversal is allowed.

The problem I am facing is with the O(1)space solution. Had there not been this constraint, it could have been easily solved.

Answer 1

The only way this can be done in space O(1) is if the nodes know their parent. Otherwise you cannot even traverse the tree unless there is some additional aid. However with this constraint it's again easy and back to tree-traversal, but without recursion. The tricky part is probably knowing which tree-path you came from when you go from a node to its parent (p) and cannot store this information as this would require O(log N) space. However, you know the last value you outputted. If it is smaller than the one of p, go the right, otherwise go to p’s parent.