Two easy to understand C++ pre-order traversal solution (recursive and iterative) with demo

• Recursive solution

``````class Solution {
private:
TreeNode* pre = NULL;

public:
void flatten(TreeNode* root) {
if(!root) return;
pre = root;

TreeNode* right = root->right;
if(root->left) root->right = root->left;
flatten(root->left);
pre->right = right;
flatten(root->right);

root->left = NULL;
}
};
``````

Iterative solution: Starting from parent node `runner`, keep a copy of right child, let it be `right` first since we are going to reset `runner->right`: if runner has `left child`(`runner->left`), it will become the new right child of runner, and then we set `left child` to `nullptr`. How to deal the old right child `right`? We need to find it a new parent, which should be the rightmost node in the subtree rooted at the old left child, which we just set as the new right child(`runner->right`), so rRunner is doing this work to find the new parent for right. After all of this, we continue with runner's right child.

``````current runner: 1

before update:
1
/ \
2   5
/ \   \
3   4   6

update:
right = 1->right = 5
1->right = 2
rRunner = 4
4->right = right = 5

after update:
1
\
2
/ \
3   4
\
5
\
6

next runner: 2
``````

Code

``````class Solution {
public:
void flatten(TreeNode* root) {
TreeNode* runner = root;

while(runner){
if(runner->left){
TreeNode* right = runner->right;
runner->right = runner->left;
runner->left = nullptr;
runner = runner->right;

TreeNode* rRunner = runner;
while(rRunner->right){
rRunner = rRunner->right;
}
rRunner->right = right;  /*rRunner is the new parent of `right`*/
}else{
runner = runner->right;
}
}
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.