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

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

Leave a Reply

Your email address will not be published.