Leetcode: Increasing Order Search Tree

This question is asked at both Amazon and Apple.  

Given the root of a binary search tree, rearrange the tree in-order so the leftmost node in the tree is now the root of the tree and every node has no left child and only one right child. 

We just want to output the entire order of the tree from left to right. 

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9] 

Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

Here's the data structure:

struct TreeNode {

    int val; 

    TreeNode * left; 

    TreeNode *right; 

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right){}    

}

I believe the : emphasizes a return value. But before, let's talk about member initializer lists in C++. 

These are constructor member initializer list. 

Here is the constructor original way: 

public: 

    Entity() {

    }

    Entity(const std::string& name) {

        m_Name = name;

    }

We can write the colon, and list of the stuff I have to initialize which replaces the need to assign to constructor. 

public: 

    Entity(): m_Name("Unknown"), x(0), y(0), z(0) {

    Init(); 

}

So, let's try to figure out skill on how to solve this. We will recursively call function increasingBST. 

We recursively call the root.left, root to change the left subtree into linked list + current node. 

So we get increasingBST(root.left) + root + increasingBST(root.right). 

We should arrange the old tree, now create a new tree. 

We have to set the left and right. We also need to know the root now. 

The root is whatever is from the left to the root. We set the right to anything from root.right to tail. Here is the code: 

TreeNode* increasingBST(TreeNode* root, TreeNode* tail = NULL) {

    //if we don't have a root we return the tail node. 

    if(!root) return tail;

    //left subtree. Go all the way to the left subtree set this. 

    TreeNode* res = increasingBST(root -> left, root); 

    root->left = NULL;

    //right subtree. After reaching root again, then set this tree to the right and spread things out again. 

    root-> right = increasingBST(root-> right, tail); 

    //this will be the root of the brand new tree. 

    return res;

}

Inorder you go from left to root to right. It goes through the left subtree first, then has all the right subtree and returns the top node of the left subtree.