What 's the best solution to find an element in a deepest binary tree
1
Recently, I had an interview question and it was about finding element in a binary tree, I code both recusive and iteratif solution with c# but the problem was that in test cases when we have a tree with 1000000 node and all of them are on the left side. the interviewer said to me that my solutions (recusive and iteratif) don't save memory RAM enough for this case and i don't understand how to improve my solution
// recusive Mode
public Node Find(int v)
{
if(v == value)
{
return this;
}else if(v <value){
if (left == null) return null;
return left.Find(v);
}else{
if (right == null) return null;
return right.Find(v);
}
}
// iterative
public Node Find(int v)
{
Node current = this;
while(value != v && current != null)
{
if (v < current.value)
{
if (current.left == null){ current = null};
else{current = current.left};
}
else
{
if (current.right == null) { current = null};
else{current = current.right };
}
}
return current;
}
I need some advices to solve this kind of issue ?
c# algorithm recursion iteration binary-tree
asked Nov 26 '18 at 7:43
Kamel BOUYACOUBKamel BOUYACOUB
1411213
add a comment |
1
Recently, I had an interview question and it was about finding element in a binary tree, I code both recusive and iteratif solution with c# but the problem was that in test cases when we have a tree with 1000000 node and all of them are on the left side. the interviewer said to me that my solutions (recusive and iteratif) don't save memory RAM enough for this case and i don't understand how to improve my solution
// recusive Mode
public Node Find(int v)
{
if(v == value)
{
return this;
}else if(v <value){
if (left == null) return null;
return left.Find(v);
}else{
if (right == null) return null;
return right.Find(v);
}
}
// iterative
public Node Find(int v)
{
Node current = this;
while(value != v && current != null)
{
if (v < current.value)
{
if (current.left == null){ current = null};
else{current = current.left};
}
else
{
if (current.right == null) { current = null};
else{current = current.right };
}
}
return current;
}
I need some advices to solve this kind of issue ?
c# algorithm recursion iteration binary-tree
asked Nov 26 '18 at 7:43
Kamel BOUYACOUBKamel BOUYACOUB
1411213
Neither, iterative nor recursive allocate memory in the heap. So I don't understand how they can save more RAM memory. However the recursive version allocates stack memory on each call. The iterative version needs just a few bytes to hold its local variableNode current
– Jesús López
Nov 26 '18 at 8:36
You mean binary search tree right? otherwise, your algo will not work for normal binary tree.
– Pham Trung
Nov 26 '18 at 9:01
add a comment |
1
1
1
Recently, I had an interview question and it was about finding element in a binary tree, I code both recusive and iteratif solution with c# but the problem was that in test cases when we have a tree with 1000000 node and all of them are on the left side. the interviewer said to me that my solutions (recusive and iteratif) don't save memory RAM enough for this case and i don't understand how to improve my solution
// recusive Mode
public Node Find(int v)
{
if(v == value)
{
return this;
}else if(v <value){
if (left == null) return null;
return left.Find(v);
}else{
if (right == null) return null;
return right.Find(v);
}
}
// iterative
public Node Find(int v)
{
Node current = this;
while(value != v && current != null)
{
if (v < current.value)
{
if (current.left == null){ current = null};
else{current = current.left};
}
else
{
if (current.right == null) { current = null};
else{current = current.right };
}
}
return current;
}
I need some advices to solve this kind of issue ?
c# algorithm recursion iteration binary-tree
asked Nov 26 '18 at 7:43
Kamel BOUYACOUBKamel BOUYACOUB
1411213
Recently, I had an interview question and it was about finding element in a binary tree, I code both recusive and iteratif solution with c# but the problem was that in test cases when we have a tree with 1000000 node and all of them are on the left side. the interviewer said to me that my solutions (recusive and iteratif) don't save memory RAM enough for this case and i don't understand how to improve my solution
// recusive Mode
public Node Find(int v)
{
if(v == value)
{
return this;
}else if(v <value){
if (left == null) return null;
return left.Find(v);
}else{
if (right == null) return null;
return right.Find(v);
}
}
// iterative
public Node Find(int v)
{
Node current = this;
while(value != v && current != null)
{
if (v < current.value)
{
if (current.left == null){ current = null};
else{current = current.left};
}
else
{
if (current.right == null) { current = null};
else{current = current.right };
}
}
return current;
}
I need some advices to solve this kind of issue ?
c# algorithm recursion iteration binary-tree
c# algorithm recursion iteration binary-tree
asked Nov 26 '18 at 7:43
Kamel BOUYACOUBKamel BOUYACOUB
1411213
asked Nov 26 '18 at 7:43
Kamel BOUYACOUBKamel BOUYACOUB
1411213
edited Nov 26 '18 at 7:53
Kamel BOUYACOUB
asked Nov 26 '18 at 7:43
Kamel BOUYACOUBKamel BOUYACOUB
1411213
asked Nov 26 '18 at 7:43
Kamel BOUYACOUBKamel BOUYACOUB
1411213
asked Nov 26 '18 at 7:43
Kamel BOUYACOUBKamel BOUYACOUB
1411213
1411213
Neither, iterative nor recursive allocate memory in the heap. So I don't understand how they can save more RAM memory. However the recursive version allocates stack memory on each call. The iterative version needs just a few bytes to hold its local variableNode current
– Jesús López
Nov 26 '18 at 8:36
You mean binary search tree right? otherwise, your algo will not work for normal binary tree.
– Pham Trung
Nov 26 '18 at 9:01
add a comment |
Neither, iterative nor recursive allocate memory in the heap. So I don't understand how they can save more RAM memory. However the recursive version allocates stack memory on each call. The iterative version needs just a few bytes to hold its local variableNode current
– Jesús López
Nov 26 '18 at 8:36
You mean binary search tree right? otherwise, your algo will not work for normal binary tree.
– Pham Trung
Nov 26 '18 at 9:01
Neither, iterative nor recursive allocate memory in the heap. So I don't understand how they can save more RAM memory. However the recursive version allocates stack memory on each call. The iterative version needs just a few bytes to hold its local variable
Node current– Jesús López
Nov 26 '18 at 8:36
Neither, iterative nor recursive allocate memory in the heap. So I don't understand how they can save more RAM memory. However the recursive version allocates stack memory on each call. The iterative version needs just a few bytes to hold its local variable
Node current– Jesús López
Nov 26 '18 at 8:36
You mean binary search tree right? otherwise, your algo will not work for normal binary tree.
– Pham Trung
Nov 26 '18 at 9:01
You mean binary search tree right? otherwise, your algo will not work for normal binary tree.
– Pham Trung
Nov 26 '18 at 9:01
add a comment |
1 Answer
1
active
oldest
votes
3
Your iterative solution has some bugs in it.
// iterative
public Node Find(int v)
{
Node current = this;
// Here you need to compare current.value instead of just value
// Also, to use short-circuiting you need to put null-check first
// otherwise you might access current.value while current is null
while(current != null && current.value != v)
{
if (v < current.value)
{
//if (current.left == null){ current = null};
//else{current = current.left};
current = current.left; // the same as two commented out lines
}
else
{
//if (current.right == null) { current = null};
//else{current = current.right };
current = current.right; // the same as two commented out lines
}
}
return current;
}
answered Nov 26 '18 at 8:10
YolaYola
11.2k64672
add a 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
});
}
});
draft saved
draft discarded
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%2f53476615%2fwhat-s-the-best-solution-to-find-an-element-in-a-deepest-binary-tree%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
3
Your iterative solution has some bugs in it.
// iterative
public Node Find(int v)
{
Node current = this;
// Here you need to compare current.value instead of just value
// Also, to use short-circuiting you need to put null-check first
// otherwise you might access current.value while current is null
while(current != null && current.value != v)
{
if (v < current.value)
{
//if (current.left == null){ current = null};
//else{current = current.left};
current = current.left; // the same as two commented out lines
}
else
{
//if (current.right == null) { current = null};
//else{current = current.right };
current = current.right; // the same as two commented out lines
}
}
return current;
}
answered Nov 26 '18 at 8:10
YolaYola
11.2k64672
add a comment |
3
Your iterative solution has some bugs in it.
// iterative
public Node Find(int v)
{
Node current = this;
// Here you need to compare current.value instead of just value
// Also, to use short-circuiting you need to put null-check first
// otherwise you might access current.value while current is null
while(current != null && current.value != v)
{
if (v < current.value)
{
//if (current.left == null){ current = null};
//else{current = current.left};
current = current.left; // the same as two commented out lines
}
else
{
//if (current.right == null) { current = null};
//else{current = current.right };
current = current.right; // the same as two commented out lines
}
}
return current;
}
answered Nov 26 '18 at 8:10
YolaYola
11.2k64672
add a comment |
3
3
3
Your iterative solution has some bugs in it.
// iterative
public Node Find(int v)
{
Node current = this;
// Here you need to compare current.value instead of just value
// Also, to use short-circuiting you need to put null-check first
// otherwise you might access current.value while current is null
while(current != null && current.value != v)
{
if (v < current.value)
{
//if (current.left == null){ current = null};
//else{current = current.left};
current = current.left; // the same as two commented out lines
}
else
{
//if (current.right == null) { current = null};
//else{current = current.right };
current = current.right; // the same as two commented out lines
}
}
return current;
}
answered Nov 26 '18 at 8:10
YolaYola
11.2k64672
Your iterative solution has some bugs in it.
// iterative
public Node Find(int v)
{
Node current = this;
// Here you need to compare current.value instead of just value
// Also, to use short-circuiting you need to put null-check first
// otherwise you might access current.value while current is null
while(current != null && current.value != v)
{
if (v < current.value)
{
//if (current.left == null){ current = null};
//else{current = current.left};
current = current.left; // the same as two commented out lines
}
else
{
//if (current.right == null) { current = null};
//else{current = current.right };
current = current.right; // the same as two commented out lines
}
}
return current;
}
answered Nov 26 '18 at 8:10
YolaYola
11.2k64672
answered Nov 26 '18 at 8:10
YolaYola
11.2k64672
answered Nov 26 '18 at 8:10
YolaYola
11.2k64672
answered Nov 26 '18 at 8:10
YolaYola
11.2k64672
11.2k64672
add a comment |
add a comment |
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f53476615%2fwhat-s-the-best-solution-to-find-an-element-in-a-deepest-binary-tree%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
Neither, iterative nor recursive allocate memory in the heap. So I don't understand how they can save more RAM memory. However the recursive version allocates stack memory on each call. The iterative version needs just a few bytes to hold its local variable
Node current– Jesús López
Nov 26 '18 at 8:36
You mean binary search tree right? otherwise, your algo will not work for normal binary tree.
– Pham Trung
Nov 26 '18 at 9:01