[Programming Problem] Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree into a “linked list”:

– The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.

– The “linked list” should be in the same order as a pre-order traversal of the binary tree.

[Problem Link]

Recursively run through the whole tree. During return of the recursion, root.right is set to left_linked_list (return from left recursion) and the end of left_linked_list.right is set to right_linked_list (return from right recursion). One gotcha, is the need to account for left_linked_list being empty/null. Also, don’t forget to set root.left to null.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
 
var lastEl = function(root) {
    let curr = root;
    while (curr.right !== null) curr = curr.right;
    return curr;
}
 
 
var flatten = function(root) {
    if (!root) return null;
 
    let leftLL = flatten(root.left);
    let rightLL = flatten(root.right);
 
    root.left = null;
    //root.right = null;
 
    if (leftLL) {
        root.right = leftLL;
        lastEl(leftLL).right = rightLL;
    } else {
        root.right = rightLL;
    }
 
    return root;
};

softwareeveryday

184 thoughts on “[Programming Problem] Flatten Binary Tree to Linked List”

  2. I wish to convey my affection for your generosity giving support to persons that really need assistance with the issue. Your real dedication to passing the solution all-around was incredibly interesting and have all the time encouraged regular people just like me to get to their desired goals. Your personal warm and friendly guide entails so much to me and further more to my office colleagues. With thanks; from each one of us.

    Reply

  3. I must get across my admiration for your generosity giving support to all those that need help on the idea. Your very own dedication to getting the solution across had become definitely insightful and have always encouraged men and women just like me to arrive at their dreams. Your new useful useful information signifies a whole lot to me and further more to my peers. Best wishes; from everyone of us.

    Reply

  4. I wish to voice my affection for your kind-heartedness giving support to persons who need help on in this issue. Your real dedication to getting the solution all over had become really helpful and has continuously permitted those much like me to get to their aims. Your warm and friendly tips and hints entails a whole lot to me and somewhat more to my colleagues. With thanks; from all of us.

    Reply

  5. I precisely wanted to thank you very much yet again. I’m not certain what I would have used in the absence of the type of pointers provided by you concerning such subject. This has been a real terrifying setting in my view, nevertheless encountering a new professional form you handled that took me to jump with contentment. Now i’m grateful for your help and thus wish you comprehend what an amazing job that you’re carrying out educating people today using your websites. I’m certain you’ve never come across any of us.

    Reply

  6. I must voice my gratitude for your generosity in support of people who need guidance on that topic. Your real commitment to passing the solution all-around ended up being really insightful and have regularly enabled those like me to get to their goals. Your new interesting useful information implies much a person like me and far more to my peers. Regards; from all of us.

    Reply

  7. Thanks a lot for giving everyone a very breathtaking opportunity to discover important secrets from here. It is usually so brilliant and also full of a great time for me personally and my office mates to visit your website really thrice every week to find out the newest secrets you will have. Of course, we’re usually pleased with the remarkable suggestions you give. Certain two points in this article are honestly the simplest we have all ever had.

    Reply

  8. I would like to convey my affection for your kindness in support of individuals who really need help on in this content. Your personal dedication to getting the solution around ended up being certainly important and has regularly allowed individuals much like me to attain their desired goals. Your helpful help indicates a great deal a person like me and far more to my fellow workers. Thanks a ton; from everyone of us.

    Reply

  9. I truly wanted to jot down a simple comment to be able to thank you for some of the pleasant advice you are writing here. My time consuming internet investigation has finally been recognized with reasonable facts to share with my friends and family. I ‘d state that that many of us readers actually are truly blessed to exist in a good place with many perfect people with very beneficial things. I feel really grateful to have encountered the site and look forward to many more exciting moments reading here. Thanks once more for a lot of things.

    Reply

  10. I precisely needed to say thanks all over again. I’m not certain the things I would’ve gone through without these creative concepts provided by you directly on my industry. It had become a real intimidating dilemma for me personally, however , taking a look at the expert mode you managed that took me to leap over contentment. I’m happy for the help and even pray you are aware of a great job you’re accomplishing educating people today via a web site. More than likely you haven’t come across all of us.

    Reply

  11. I want to point out my appreciation for your generosity for individuals that actually need help on that idea. Your very own dedication to passing the solution along ended up being quite beneficial and have usually enabled some individuals like me to arrive at their objectives. Your entire useful help means a lot a person like me and far more to my fellow workers. Thanks a lot; from everyone of us.

    Reply

  12. My spouse and i have been really fortunate when Jordan could do his web research through the ideas he discovered from your very own weblog. It is now and again perplexing to simply always be releasing secrets and techniques that many men and women could have been selling. We really take into account we now have you to appreciate for that. The type of explanations you have made, the easy site menu, the friendships you can help to promote – it’s everything superb, and it is aiding our son in addition to the family understand that content is interesting, and that’s quite indispensable. Many thanks for everything!

    Reply

  13. Thanks so much for providing individuals with an exceptionally spectacular opportunity to read from here. It really is very kind and also packed with a great time for me and my office peers to search the blog on the least three times weekly to study the newest secrets you have got. And definitely, I’m so certainly impressed with your cool tips served by you. Some 3 points in this post are without a doubt the simplest we have ever had.

    Reply

  14. I must show my gratitude for your kind-heartedness in support of men who need guidance on that concept. Your special commitment to passing the solution all-around has been wonderfully insightful and have frequently permitted associates just like me to arrive at their dreams. Your own warm and friendly publication denotes a whole lot a person like me and somewhat more to my office workers. Regards; from all of us.

    Reply

  15. I actually wanted to develop a comment to be able to appreciate you for all of the marvelous tricks you are giving out at this site. My time consuming internet search has finally been compensated with high-quality tips to exchange with my company. I would point out that many of us readers actually are very much lucky to live in a really good site with so many perfect people with valuable secrets. I feel truly lucky to have seen your entire web pages and look forward to so many more entertaining moments reading here. Thanks again for a lot of things.

    Reply

  20. I wish to point out my gratitude for your generosity supporting men who actually need assistance with this particular idea. Your personal dedication to passing the message up and down became pretty helpful and has all the time enabled ladies much like me to arrive at their desired goals. The insightful advice can mean this much to me and substantially more to my office colleagues. Thank you; from everyone of us.

    Reply

  24. My wife and i have been really satisfied when Ervin managed to carry out his inquiry via the ideas he made through the web pages. It is now and again perplexing to just continually be giving away methods that people may have been trying to sell. And we also consider we’ve got the writer to appreciate for that. The entire explanations you made, the easy blog navigation, the relationships you will assist to instill – it is everything remarkable, and it’s really facilitating our son in addition to us do think that issue is thrilling, which is certainly extraordinarily indispensable. Thank you for all the pieces!

    Reply

  26. Thanks a lot for providing individuals with such a memorable opportunity to read critical reviews from here. It is usually very sweet and as well , stuffed with fun for me personally and my office acquaintances to search your website really three times in a week to read the fresh tips you have. And of course, I am also certainly happy for the extraordinary opinions served by you. Some 3 tips in this post are unquestionably the best we’ve had.

    Reply

  27. I precisely wanted to thank you so much once again. I do not know the things that I could possibly have taken care of without the type of basics documented by you on such question. It previously was a very distressing crisis in my view, however , noticing this well-written style you handled that took me to jump over delight. Now i am grateful for this guidance and in addition trust you are aware of a powerful job you were carrying out instructing many people by way of your website. I know that you’ve never come across all of us.

    Reply

  50. I simply wished to say thanks again. I am not sure the things that I would have carried out without the type of methods discussed by you over such area of interest. This has been an absolute traumatic difficulty for me personally, but witnessing this expert avenue you dealt with the issue made me to weep over fulfillment. Extremely happy for your support and thus believe you are aware of an amazing job you happen to be doing educating others all through a site. I’m certain you have never met all of us.

    Reply

  55. I have to get across my gratitude for your kind-heartedness giving support to men and women who must have help on your area of interest. Your personal dedication to passing the message along has been rather invaluable and have always helped folks much like me to arrive at their aims. Your new invaluable help and advice denotes much a person like me and especially to my colleagues. Best wishes; from all of us.

    Reply

  61. I wanted to send you that bit of note to help say thank you yet again considering the lovely suggestions you’ve shown on this site. It’s so incredibly generous of you giving extensively all that most of us would have advertised for an ebook to end up making some profit on their own, mostly given that you could possibly have done it if you decided. Those ideas additionally acted as the fantastic way to be aware that some people have a similar desire really like my personal own to find out great deal more on the topic of this problem. I am certain there are numerous more pleasurable occasions in the future for people who look over your site.

    Reply

  80. |Avoid any horizontal stripes if your weight is higher. This puts emphasis on how wide your body is, making it look even wider. Instead, pick a pattern that is linear or vertical which can make you look thinner.

    Reply

  84. I definitely wanted to construct a comment to be able to thank you for these splendid advice you are giving at this site. My time intensive internet look up has now been rewarded with wonderful information to go over with my companions. I ‘d declare that many of us visitors actually are rather blessed to be in a good site with very many special individuals with good solutions. I feel very privileged to have come across your entire website and look forward to some more exciting minutes reading here. Thank you once more for everything.

    Reply

  87. Thanks a lot for giving everyone an exceptionally spectacular opportunity to check tips from here. It’s usually very useful and as well , stuffed with a lot of fun for me and my office friends to visit your website at the least thrice in one week to read the newest guidance you will have. And lastly, we’re certainly happy with all the mind-blowing things served by you. Certain 2 ideas in this article are rather the most impressive we have all had.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

[Programming Problem] Subsets II
Read More
[Programming Problem] Largest Number
Read More
[Programming Problem] Sum Root to Leaf Numbers
Read More