Can you improve upon my recursive approach?


  • 12
    S

    I am basically storing the last visited pre-order traversal node in a static "lastVisited" TreeNode, and re-assigning its children.
    Can my algorithm be improved so that we don't need that static variable, and all is handled by the recursive algorithm.

    private static TreeNode lastVisited = null;
    
    public static void flattenHelper(TreeNode root) {
        if(root == null)
            return;
    
        TreeNode savedRight = root.right;
        if(lastVisited != null) {
            lastVisited.left = null;
            lastVisited.right = root;
        }
        lastVisited = root;
        
        flattenHelper(root.left);
        flattenHelper(savedRight);
    }

  • 0
    T

    I believe one has to store the lastVisited node in some form, for the recursive approach to work.
    Or, if you're using java, then use some container object i.e.- 'foo'(which contains the lastVisited) & keep passing it into each recursive call, whereupon you may invoke helper function & modify, lastVisited something like:

    flattenHelper(<TreeNode *> node, <foo> holderObj);
    
    holderObj.lastVisited = updatedNodeObj;
    

    Although, foo itself shall be passed as obj always, but it's elements would serve the purpose of references which are mutable.


  • 0
    S

    Your answer makes sense. I agree for Java using a container object is a very good alternative to using a static variable.
    My question however was to implement an algorithm where we do not need to use a static/wrapper variable, but update a variable at every call.
    Something like this, but I couldnt understand his algo, and I think mine is very simple.
    [http://discuss.leetcode.com/questions/280/flatten-binary-tree-to-linked-list][url]


  • 75
    U

    It's not good to use recursive approach, as it's not in-place.

    while ( root ) {
    	if ( root->left ) {
    		TreeNode *ptr = root->left;
    		while ( ptr->right ) ptr = ptr->right;
    		ptr->right = root->right;
    		root->right = root->left;
    		root->left = NULL;
    	}
    	root = root->right;
    }

  • 0
    S

    Elegant method!

    Btw,i wonder why recursive approach is not in-place?

    recursive function calls results stacks of TreeNode*, not TreeNode?


  • 0
    U

    Recursion will use the stack, so it's not in place.


  • 0
    Q

    Very beautiful code!
    But when I run this non-recursive method, it took nearly twice time (~= 52ms) compared to the recursive method (~=24ms). I think that's because this non-recursive method visits the right side of left subtree lots of times. But the recursive method only visits each node once.


  • 0
    L
    void flatten(TreeNode* root){
    	if(root == NULL) return;
    	TreeNode *saved_right = root -> right, *ptr = root;
    	root -> right = root -> left;
    	root -> left = NULL;
    	while(ptr -> right != NULL) ptr = ptr -> right;
    	ptr -> right = saved_right;
    	flatten(root -> right);
    	return;
    }
    

    Does this also use stack?


  • 0
    L

    Looks short and elegant, but it's tricky and not easy to understand. Should not consider good code in real project.
    I would suggest to remove that TimeLimited test case if possible as readability should be more important than gain a little speed.


  • 0
    H

    my recursive approach is like this : get the left tree done, then the right tree. always return the tree's 'rightest' node.

    public void flatten(TreeNode root) {
    	if (root == null) {
    		return;
    	}
    	set(root);
    }
    
    public TreeNode set(TreeNode root) {
    	if (root.left == null && root.right == null) {
    		return root;
    	}
    
    	TreeNode left = null;
    	if (root.left != null) {
    		left = set(root.left);
    	}
    	TreeNode right = null;
    	if (root.right != null) {
    		right = set(root.right);
    	}
    	
    	if (left != null) {
    		TreeNode temp = root.right;
    		root.right = root.left;
    		root.left = null;
    		left.right = temp;
    	}
    
    	if (right != null) {
    		return right;
    	} else {
    		return left;
    	}
    }

  • 0
    R

    Yes and no depending if the compiler is able to optimize it or no.
    You have a recursive call, but at the end of your method and is always called.
    You can easily convert it to a simple loop, but also the compiler may do the same for you:
    http://en.wikipedia.org/wiki/Tail_call


  • 8
    R

    I just improved the solution of user20:

    • Commented and assigns to variable human-friendly names.
    • I converted the tail-call to a loop, no recursion.
    • Same complexity, O(NlogN) i think.

    What do you think?

    void flatten(TreeNode* root) {
        
        if (!root) return;
        
        TreeNode* node = root;
        while (node) {
        
            // Attatches the right sub-tree to the rightmost leaf of the left sub-tree:
            if (node->left) {
                
                TreeNode *rightMost = node->left;
                while (rightMost->right) {
                    
                    rightMost = rightMost->right;
                }
                rightMost->right = node->right;
    
                // Makes the left sub-tree to the right sub-tree:
                node->right = node->left;
                node->left = nullptr;
            }
    
            // Flatten the rest of the tree:
            node = node->right;
        }    
    }
    

  • 4
    Y

    Here is my solution ,using an extra pointer oldptr to change the relationship of the nodes during pre-order travesal. The running time is about 24ms.

    class Solution {
        public:
            void flatten(TreeNode *root) {
                 stack<TreeNode *> stk;
                 if(root==NULL) 
                    return;
                 
                 stk.push(root);
                 TreeNode *oldptr=NULL;
                 
                 while(!stk.empty()){            // preorder traversal using a stack
                     TreeNode *ptr=stk.top();    // Using ptr to do travesal 
                     stk.pop();
                     if(ptr->right) 
                        stk.push(ptr->right);
                     if(ptr->left) 
                        stk.push(ptr->left);
                     if(oldptr!=NULL){            // Using oldptr to change left and right pointer 
                        oldptr->left=NULL;
                        oldptr->right=ptr;
                     }
                     oldptr=ptr;
                 }
                
            }
        };

  • 0
    C

    amazing method!


  • 0
    M
    This post is deleted!

  • 0
    T

    @user20 I think there is a mistake in your code. Please see the solution I have added.


  • 0
    T
    class Solution:
    
        def flatten(self, root):
            while root:
                if root.left:
                    node = root.left
                    while True:
                        if node.right:
                            node = node.right
                        elif node.left:
                            node = node.left
                        else:
                            break
                    node.right = root.right
                    root.right = root.left
                    root.left = None
    
                root = root.right
    

    This is the same as other non-recursive solutions in this thread, with one correction. In the if root.left: part, you basically need to find the last node of the pre-order traversal of the left subtree, so that you can attach the right subtree to its right branch. The way to find the last element in a pre-order traversal is as follows.

    while True:
        if node.right:
            node = node.right
        elif node.left:
            node = node.left
        else:
            break
    

    Keep going down the tree, preferring the right branch. Other solutions in this thread simply keep going down the right branch. Surprisingly, such a solution also passes the judge.


  • 0
    U

    Hmm. It looks good.

    The only comment I have is that its complexity is O(N) but not O(N log N).


  • 0
    J

    Brilliant solution.


  • 0
    V

    Iterative version using stack O(n) time complexity as every node is visited exactly once, O(n) space complexity for stack.

    public class Solution {
        public void flatten(TreeNode root) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode p = root;
     
            while(p != null || !stack.empty()){
     
                if(p.right != null){
                    stack.push(p.right);
                }
     
                if(p.left != null){
                    p.right = p.left;
                    p.left = null;
                }else if(!stack.empty()){
                    TreeNode temp = stack.pop();
                    p.right=temp;
                }
     
                p = p.right;
            }
        }
    }

Log in to reply
 

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