# Java Solution Recursive & Non-Recursive

• I am ambiguous about if "recursive" is qualified for "in place", as sb in discussion says it's NOT.
Here I have Java solution in recursive and non-recursive.

``````/**
* Move from root down,
* for each node,
*  attach original right as the right child of the rigthmost node of left subtree,
*  set original left as new right child.
* repeat with next right child.
*/
/// SOLUTION II: non-recursive ///
public void flatten(TreeNode root) {
TreeNode node = root;
while (node != null) {
TreeNode left = node.left;
TreeNode right = node.right;
if (left != null) {
TreeNode temp = left;
while (temp.right != null)
temp = temp.right;
temp.right = right;
node.right = left;
node.left = null;
}
node = node.right;
}
}

/// SOLUTION I: accepted, recursion ///
public void flatten(TreeNode root) {
if (root == null)
return;
TreeNode left = root.left;
TreeNode right = root.right;
if (left != null) {
TreeNode rightmost = getRightmost(left);
rightmost.right = right;
root.left = null; // CATCH: must set left to null explicitly
root.right = left;
}
flatten(root.right);
}

// return the rightmost node of a subtree;
// node must not be null.
private TreeNode getRightmost(TreeNode node) {
while (node.right != null)
node = node.right;
return node;
}``````

• I think the word "in-place" means that one does not create new nodes for the result, but simply change the pointers of nodes in-place.

• This is the clearest solution I've ever seen. Easy to understand. Very smart. Thanks!

• Your iterative solution is so clear! Thanks for sharing.

• @AlexTheGreat You non-recursive solution is so easy to understand. Thx

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