Given the root of a binary tree, the task is to flatten the tree into a linked list using the same TreeNode class. The left child pointer of each node in the linked list should always be NULL, and the right child pointer should point to the next node in the linked list. The nodes in the linked list should be in the same order as that of the preo…

flatten-binary-tree.js

// Definition of a binary tree node
// class TreeNode {
//   constructor(data) {
//     this.data = data;
//     this.left = null;
//     this.right = null;
//   }
// }

export function flattenTree(root) {
  // start at root node
  let current = root;

  // end loop when we arrive at null
  // current only shifts to the right (current always becomes current.right, never current.eft)
  while (current) {
    // find right most in the left subtree
    let next = current.left;
    // move right from the left node if there is a left node
    while (next && next.right) {
      next = next.right;
    }

    // if there is a rightmost node in the left subtree,
    // move right subtree of the current node to the right of the rightmost node
    // move left subtree of the current node to the right of the current node
    // nullify left child of the current node
    if (next) {
      next.right = current.right;
      current.right = current.left;
      current.left = null;
    }

    // shift to the next right node
    current = current.right;
  }

  return root;
}

// tc: O(n) where n is the number of nodes
// sc: O(1)