[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;
};

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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. 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.

  10. 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.

  11. 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!

  12. 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.

  13. 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.

  14. 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.

Leave a Reply

Your email address will not be published.