897. Increasing Order Search Tree

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

Example 1:
Input: [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]

Constraints: The number of nodes in the given tree will be between 1 and 100. Each node will have a unique integer value from 0 to 1000.

Further reading:

What is linked list?

• like arrays - linear data structure; elements are linked to pointers.
• drawbacks of array: fixed, upperlimit in advance. same memory usage - irrespective of elements stored or not.
• inserting new element in b/w is expensive.

Why to use linked list

• dynamic size and ease of insertion.
• drawbacks: random access not possible, sequence, extra space for every element(pointer).
• not cachy friendly.