Java Solution Recursive & Non-Recursive

  • 10

    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)
        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;
    // 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;

  • 1

    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.

  • 0

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

  • 0

    Your iterative solution is so clear! Thanks for sharing.

  • 0

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

Log in to reply

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