Mirror binary tree with private left and right subtrees
There's tons of info on how to mirror it, but those assume that node->left and node->right can be modified, such as this function (not mine, copied from another website).
void mirror(struct Node* node) {
if (node==NULL) return;
else {
struct Node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
I know there has to be recursion and a base case (basically the "do the subtrees" part) but I have no idea how to do the actual swapping since Node is a class with the left and right subtrees being private (can't change that).
For reference, this is the class constructor (there's no default constructor). I can provide more functions if they're important (there are accessor functions but no mutators). It also uses templates, hence the T.
Node(const T &x, Node *L = 0, Node *R = 0) : data(x), left(L), right(R) {}
I also made two other functions (treeHeight and countNodes), don't know if that's relevant. And I have to make a new tree to return, not modify the original tree.
Note - I did not want to provide this as an answer but wanted to inform the OP about C++ syntax
You originally had this for your function:
void mirror(struct Node* node) {
if (node==NULL) return;
else {
struct Node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
In C++ you do not need to use the keyword struct when declaring it as a function-parameter nor as a declaration of a variable. You only need it when you are writing the declaration to the struct or class itself. You can simply do this:
void mirror(Node* node) {
if (node==NULL) return;
else {
Node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
c++ binary-tree
edited Nov 26 '18 at 8:50
Francis Cugler
4,60911227
asked Nov 26 '18 at 7:01
Karan BijaniKaran Bijani
12
add a comment |
There's tons of info on how to mirror it, but those assume that node->left and node->right can be modified, such as this function (not mine, copied from another website).
void mirror(struct Node* node) {
if (node==NULL) return;
else {
struct Node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
I know there has to be recursion and a base case (basically the "do the subtrees" part) but I have no idea how to do the actual swapping since Node is a class with the left and right subtrees being private (can't change that).
For reference, this is the class constructor (there's no default constructor). I can provide more functions if they're important (there are accessor functions but no mutators). It also uses templates, hence the T.
Node(const T &x, Node *L = 0, Node *R = 0) : data(x), left(L), right(R) {}
I also made two other functions (treeHeight and countNodes), don't know if that's relevant. And I have to make a new tree to return, not modify the original tree.
Note - I did not want to provide this as an answer but wanted to inform the OP about C++ syntax
You originally had this for your function:
void mirror(struct Node* node) {
if (node==NULL) return;
else {
struct Node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
In C++ you do not need to use the keyword struct when declaring it as a function-parameter nor as a declaration of a variable. You only need it when you are writing the declaration to the struct or class itself. You can simply do this:
void mirror(Node* node) {
if (node==NULL) return;
else {
Node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
c++ binary-tree
edited Nov 26 '18 at 8:50
Francis Cugler
4,60911227
asked Nov 26 '18 at 7:01
Karan BijaniKaran Bijani
12
1
I made an edit and appended it at the bottom of your original question to help you with the syntax for C++ structs and classes.
– Francis Cugler
Nov 26 '18 at 8:44
add a comment |
There's tons of info on how to mirror it, but those assume that node->left and node->right can be modified, such as this function (not mine, copied from another website).
void mirror(struct Node* node) {
if (node==NULL) return;
else {
struct Node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
I know there has to be recursion and a base case (basically the "do the subtrees" part) but I have no idea how to do the actual swapping since Node is a class with the left and right subtrees being private (can't change that).
For reference, this is the class constructor (there's no default constructor). I can provide more functions if they're important (there are accessor functions but no mutators). It also uses templates, hence the T.
Node(const T &x, Node *L = 0, Node *R = 0) : data(x), left(L), right(R) {}
I also made two other functions (treeHeight and countNodes), don't know if that's relevant. And I have to make a new tree to return, not modify the original tree.
Note - I did not want to provide this as an answer but wanted to inform the OP about C++ syntax
You originally had this for your function:
void mirror(struct Node* node) {
if (node==NULL) return;
else {
struct Node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
In C++ you do not need to use the keyword struct when declaring it as a function-parameter nor as a declaration of a variable. You only need it when you are writing the declaration to the struct or class itself. You can simply do this:
void mirror(Node* node) {
if (node==NULL) return;
else {
Node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
c++ binary-tree
edited Nov 26 '18 at 8:50
Francis Cugler
4,60911227
asked Nov 26 '18 at 7:01
Karan BijaniKaran Bijani
12
There's tons of info on how to mirror it, but those assume that node->left and node->right can be modified, such as this function (not mine, copied from another website).
void mirror(struct Node* node) {
if (node==NULL) return;
else {
struct Node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
I know there has to be recursion and a base case (basically the "do the subtrees" part) but I have no idea how to do the actual swapping since Node is a class with the left and right subtrees being private (can't change that).
For reference, this is the class constructor (there's no default constructor). I can provide more functions if they're important (there are accessor functions but no mutators). It also uses templates, hence the T.
Node(const T &x, Node *L = 0, Node *R = 0) : data(x), left(L), right(R) {}
I also made two other functions (treeHeight and countNodes), don't know if that's relevant. And I have to make a new tree to return, not modify the original tree.
Note - I did not want to provide this as an answer but wanted to inform the OP about C++ syntax
You originally had this for your function:
void mirror(struct Node* node) {
if (node==NULL) return;
else {
struct Node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
In C++ you do not need to use the keyword struct when declaring it as a function-parameter nor as a declaration of a variable. You only need it when you are writing the declaration to the struct or class itself. You can simply do this:
void mirror(Node* node) {
if (node==NULL) return;
else {
Node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
c++ binary-tree
c++ binary-tree
edited Nov 26 '18 at 8:50
Francis Cugler
4,60911227
asked Nov 26 '18 at 7:01
Karan BijaniKaran Bijani
12
edited Nov 26 '18 at 8:50
Francis Cugler
4,60911227
asked Nov 26 '18 at 7:01
Karan BijaniKaran Bijani
12
edited Nov 26 '18 at 8:50
Francis Cugler
4,60911227
edited Nov 26 '18 at 8:50
Francis Cugler
4,60911227
edited Nov 26 '18 at 8:50
Francis Cugler
4,60911227
4,60911227
asked Nov 26 '18 at 7:01
Karan BijaniKaran Bijani
12
asked Nov 26 '18 at 7:01
Karan BijaniKaran Bijani
12
asked Nov 26 '18 at 7:01
Karan BijaniKaran Bijani
12
12
1
I made an edit and appended it at the bottom of your original question to help you with the syntax for C++ structs and classes.
– Francis Cugler
Nov 26 '18 at 8:44
add a comment |
1
I made an edit and appended it at the bottom of your original question to help you with the syntax for C++ structs and classes.
– Francis Cugler
Nov 26 '18 at 8:44
1
1
I made an edit and appended it at the bottom of your original question to help you with the syntax for C++ structs and classes.
– Francis Cugler
Nov 26 '18 at 8:44
I made an edit and appended it at the bottom of your original question to help you with the syntax for C++ structs and classes.
– Francis Cugler
Nov 26 '18 at 8:44
add a comment |
1 Answer
1
active
oldest
votes
I would suggest you write your own swap member function:
void swapChildren(){
temp = node->left;
node->left = node->right;
node->right = temp;
}
This swaps the left and right elements.
answered Nov 26 '18 at 7:08
M. DenningerM. Denninger
1217
This is homework, so I can't modify the Node header file. And I forgot to mention that I have to make a new tree, not modify the original tree (if that changes anything).
– Karan Bijani
Nov 26 '18 at 7:12
You could replace each Node with a new Node, in which you switch the left and right Node
– M. Denninger
Nov 26 '18 at 7:14
I assume you mean like this: Node<T>* left = node->get_right(); Node<T>* right = node->get_left(); How would I link this back to the new mirrored tree (let's say the name is mirrorTree) though?
– Karan Bijani
Nov 26 '18 at 7:17
Not like that, more like: node = new Node(node->data, node->RIGHT(), node->LEFT()); Oh, but I see that you can not modify the pointer of Node*, you would have to use Node**
– M. Denninger
Nov 26 '18 at 7:20
I figured it out: Node<T>* mirrorTree = new Node<T>(node->get_data(), mirror(node->get_right()), mirror(node->get_left())); seemed to work for me. Thanks for the help.
– Karan Bijani
Nov 26 '18 at 7:23
|
show 1 more comment
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53476105%2fmirror-binary-tree-with-private-left-and-right-subtrees%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I would suggest you write your own swap member function:
void swapChildren(){
temp = node->left;
node->left = node->right;
node->right = temp;
}
This swaps the left and right elements.
answered Nov 26 '18 at 7:08
M. DenningerM. Denninger
1217
This is homework, so I can't modify the Node header file. And I forgot to mention that I have to make a new tree, not modify the original tree (if that changes anything).
– Karan Bijani
Nov 26 '18 at 7:12
You could replace each Node with a new Node, in which you switch the left and right Node
– M. Denninger
Nov 26 '18 at 7:14
I assume you mean like this: Node<T>* left = node->get_right(); Node<T>* right = node->get_left(); How would I link this back to the new mirrored tree (let's say the name is mirrorTree) though?
– Karan Bijani
Nov 26 '18 at 7:17
Not like that, more like: node = new Node(node->data, node->RIGHT(), node->LEFT()); Oh, but I see that you can not modify the pointer of Node*, you would have to use Node**
– M. Denninger
Nov 26 '18 at 7:20
I figured it out: Node<T>* mirrorTree = new Node<T>(node->get_data(), mirror(node->get_right()), mirror(node->get_left())); seemed to work for me. Thanks for the help.
– Karan Bijani
Nov 26 '18 at 7:23
|
show 1 more comment
I would suggest you write your own swap member function:
void swapChildren(){
temp = node->left;
node->left = node->right;
node->right = temp;
}
This swaps the left and right elements.
answered Nov 26 '18 at 7:08
M. DenningerM. Denninger
1217
This is homework, so I can't modify the Node header file. And I forgot to mention that I have to make a new tree, not modify the original tree (if that changes anything).
– Karan Bijani
Nov 26 '18 at 7:12
You could replace each Node with a new Node, in which you switch the left and right Node
– M. Denninger
Nov 26 '18 at 7:14
I assume you mean like this: Node<T>* left = node->get_right(); Node<T>* right = node->get_left(); How would I link this back to the new mirrored tree (let's say the name is mirrorTree) though?
– Karan Bijani
Nov 26 '18 at 7:17
Not like that, more like: node = new Node(node->data, node->RIGHT(), node->LEFT()); Oh, but I see that you can not modify the pointer of Node*, you would have to use Node**
– M. Denninger
Nov 26 '18 at 7:20
I figured it out: Node<T>* mirrorTree = new Node<T>(node->get_data(), mirror(node->get_right()), mirror(node->get_left())); seemed to work for me. Thanks for the help.
– Karan Bijani
Nov 26 '18 at 7:23
|
show 1 more comment
I would suggest you write your own swap member function:
void swapChildren(){
temp = node->left;
node->left = node->right;
node->right = temp;
}
This swaps the left and right elements.
answered Nov 26 '18 at 7:08
M. DenningerM. Denninger
1217
I would suggest you write your own swap member function:
void swapChildren(){
temp = node->left;
node->left = node->right;
node->right = temp;
}
This swaps the left and right elements.
answered Nov 26 '18 at 7:08
M. DenningerM. Denninger
1217
answered Nov 26 '18 at 7:08
M. DenningerM. Denninger
1217
answered Nov 26 '18 at 7:08
M. DenningerM. Denninger
1217
answered Nov 26 '18 at 7:08
M. DenningerM. Denninger
1217
1217
This is homework, so I can't modify the Node header file. And I forgot to mention that I have to make a new tree, not modify the original tree (if that changes anything).
– Karan Bijani
Nov 26 '18 at 7:12
You could replace each Node with a new Node, in which you switch the left and right Node
– M. Denninger
Nov 26 '18 at 7:14
I assume you mean like this: Node<T>* left = node->get_right(); Node<T>* right = node->get_left(); How would I link this back to the new mirrored tree (let's say the name is mirrorTree) though?
– Karan Bijani
Nov 26 '18 at 7:17
Not like that, more like: node = new Node(node->data, node->RIGHT(), node->LEFT()); Oh, but I see that you can not modify the pointer of Node*, you would have to use Node**
– M. Denninger
Nov 26 '18 at 7:20
I figured it out: Node<T>* mirrorTree = new Node<T>(node->get_data(), mirror(node->get_right()), mirror(node->get_left())); seemed to work for me. Thanks for the help.
– Karan Bijani
Nov 26 '18 at 7:23
|
show 1 more comment
This is homework, so I can't modify the Node header file. And I forgot to mention that I have to make a new tree, not modify the original tree (if that changes anything).
– Karan Bijani
Nov 26 '18 at 7:12
You could replace each Node with a new Node, in which you switch the left and right Node
– M. Denninger
Nov 26 '18 at 7:14
I assume you mean like this: Node<T>* left = node->get_right(); Node<T>* right = node->get_left(); How would I link this back to the new mirrored tree (let's say the name is mirrorTree) though?
– Karan Bijani
Nov 26 '18 at 7:17
Not like that, more like: node = new Node(node->data, node->RIGHT(), node->LEFT()); Oh, but I see that you can not modify the pointer of Node*, you would have to use Node**
– M. Denninger
Nov 26 '18 at 7:20
I figured it out: Node<T>* mirrorTree = new Node<T>(node->get_data(), mirror(node->get_right()), mirror(node->get_left())); seemed to work for me. Thanks for the help.
– Karan Bijani
Nov 26 '18 at 7:23
This is homework, so I can't modify the Node header file. And I forgot to mention that I have to make a new tree, not modify the original tree (if that changes anything).
– Karan Bijani
Nov 26 '18 at 7:12
This is homework, so I can't modify the Node header file. And I forgot to mention that I have to make a new tree, not modify the original tree (if that changes anything).
– Karan Bijani
Nov 26 '18 at 7:12
You could replace each Node with a new Node, in which you switch the left and right Node
– M. Denninger
Nov 26 '18 at 7:14
You could replace each Node with a new Node, in which you switch the left and right Node
– M. Denninger
Nov 26 '18 at 7:14
I assume you mean like this: Node<T>* left = node->get_right(); Node<T>* right = node->get_left(); How would I link this back to the new mirrored tree (let's say the name is mirrorTree) though?
– Karan Bijani
Nov 26 '18 at 7:17
I assume you mean like this: Node<T>* left = node->get_right(); Node<T>* right = node->get_left(); How would I link this back to the new mirrored tree (let's say the name is mirrorTree) though?
– Karan Bijani
Nov 26 '18 at 7:17
Not like that, more like: node = new Node(node->data, node->RIGHT(), node->LEFT()); Oh, but I see that you can not modify the pointer of Node*, you would have to use Node**
– M. Denninger
Nov 26 '18 at 7:20
Not like that, more like: node = new Node(node->data, node->RIGHT(), node->LEFT()); Oh, but I see that you can not modify the pointer of Node*, you would have to use Node**
– M. Denninger
Nov 26 '18 at 7:20
I figured it out: Node<T>* mirrorTree = new Node<T>(node->get_data(), mirror(node->get_right()), mirror(node->get_left())); seemed to work for me. Thanks for the help.
– Karan Bijani
Nov 26 '18 at 7:23
I figured it out: Node<T>* mirrorTree = new Node<T>(node->get_data(), mirror(node->get_right()), mirror(node->get_left())); seemed to work for me. Thanks for the help.
– Karan Bijani
Nov 26 '18 at 7:23
|
show 1 more comment
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53476105%2fmirror-binary-tree-with-private-left-and-right-subtrees%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
I made an edit and appended it at the bottom of your original question to help you with the syntax for C++ structs and classes.
– Francis Cugler
Nov 26 '18 at 8:44