Computing the height of a tree C#
1
I have been writing this code for computing the height of a tree in c#. the input for this question would be first: the number of nodes and then the quantity for each of them. then the output would be the height of the tree.
input
5
4 -1 4 1 1
output
3
public long Solve(long nodeCount, long tree)
{
List<long> Node = new List<long>[nodeCount];
long root = 0;
for(int i =0;i<nodeCount;i++ )
{
Node[i] = new List<long>();
}
for(int j =0; j<nodeCount;j++)
{
if (tree[j] == -1)
root = j;
else
Node[tree[j]].Add(j);
}
Queue<long> Q = new Queue<long>();
Q.Enqueue(root);
long Height = 0;
while(Q.Any())
{
for(int i =0; i<Q.Count(); i++)
{
long nodee = Q.Dequeue();
if(Node[nodee] != null)
{
foreach(long N in Node[nodee])
{
Q.Enqueue(N);
}
}
}
Height = Height+1;
}
return Height;
}
this code is returning wrong results to my test cases. what is the problem?
c# tree binary-tree
asked Nov 24 '18 at 18:30
lydallydal
116
|
show 1 more comment
1
I have been writing this code for computing the height of a tree in c#. the input for this question would be first: the number of nodes and then the quantity for each of them. then the output would be the height of the tree.
input
5
4 -1 4 1 1
output
3
public long Solve(long nodeCount, long tree)
{
List<long> Node = new List<long>[nodeCount];
long root = 0;
for(int i =0;i<nodeCount;i++ )
{
Node[i] = new List<long>();
}
for(int j =0; j<nodeCount;j++)
{
if (tree[j] == -1)
root = j;
else
Node[tree[j]].Add(j);
}
Queue<long> Q = new Queue<long>();
Q.Enqueue(root);
long Height = 0;
while(Q.Any())
{
for(int i =0; i<Q.Count(); i++)
{
long nodee = Q.Dequeue();
if(Node[nodee] != null)
{
foreach(long N in Node[nodee])
{
Q.Enqueue(N);
}
}
}
Height = Height+1;
}
return Height;
}
this code is returning wrong results to my test cases. what is the problem?
c# tree binary-tree
asked Nov 24 '18 at 18:30
lydallydal
116
1
How to use your awesome Step Debugger
– Make StackOverflow Good Again
Nov 24 '18 at 18:37
@Disaffected1070452 for some reason , I can not debug
– lydal
Nov 24 '18 at 18:38
is your visual studio into debug or release mode?
– bradbury9
Nov 24 '18 at 19:07
How can a tree be an array (long tree)? Shouldn't a tree be a root Node? Each node would have a left and right. To get height you must transverse the Nodes and find the max number of nodes from root to leaves.
– jdweng
Nov 24 '18 at 20:44
@jdweng That looks like a flatenned tree, where the value of each element points to the index of its parent.
– NPras
Nov 25 '18 at 22:36
|
show 1 more comment
1
1
1
1
I have been writing this code for computing the height of a tree in c#. the input for this question would be first: the number of nodes and then the quantity for each of them. then the output would be the height of the tree.
input
5
4 -1 4 1 1
output
3
public long Solve(long nodeCount, long tree)
{
List<long> Node = new List<long>[nodeCount];
long root = 0;
for(int i =0;i<nodeCount;i++ )
{
Node[i] = new List<long>();
}
for(int j =0; j<nodeCount;j++)
{
if (tree[j] == -1)
root = j;
else
Node[tree[j]].Add(j);
}
Queue<long> Q = new Queue<long>();
Q.Enqueue(root);
long Height = 0;
while(Q.Any())
{
for(int i =0; i<Q.Count(); i++)
{
long nodee = Q.Dequeue();
if(Node[nodee] != null)
{
foreach(long N in Node[nodee])
{
Q.Enqueue(N);
}
}
}
Height = Height+1;
}
return Height;
}
this code is returning wrong results to my test cases. what is the problem?
c# tree binary-tree
asked Nov 24 '18 at 18:30
lydallydal
116
I have been writing this code for computing the height of a tree in c#. the input for this question would be first: the number of nodes and then the quantity for each of them. then the output would be the height of the tree.
input
5
4 -1 4 1 1
output
3
public long Solve(long nodeCount, long tree)
{
List<long> Node = new List<long>[nodeCount];
long root = 0;
for(int i =0;i<nodeCount;i++ )
{
Node[i] = new List<long>();
}
for(int j =0; j<nodeCount;j++)
{
if (tree[j] == -1)
root = j;
else
Node[tree[j]].Add(j);
}
Queue<long> Q = new Queue<long>();
Q.Enqueue(root);
long Height = 0;
while(Q.Any())
{
for(int i =0; i<Q.Count(); i++)
{
long nodee = Q.Dequeue();
if(Node[nodee] != null)
{
foreach(long N in Node[nodee])
{
Q.Enqueue(N);
}
}
}
Height = Height+1;
}
return Height;
}
this code is returning wrong results to my test cases. what is the problem?
c# tree binary-tree
c# tree binary-tree
asked Nov 24 '18 at 18:30
lydallydal
116
asked Nov 24 '18 at 18:30
lydallydal
116
asked Nov 24 '18 at 18:30
lydallydal
116
asked Nov 24 '18 at 18:30
lydallydal
116
asked Nov 24 '18 at 18:30
lydallydal
116
116
1
How to use your awesome Step Debugger
– Make StackOverflow Good Again
Nov 24 '18 at 18:37
@Disaffected1070452 for some reason , I can not debug
– lydal
Nov 24 '18 at 18:38
is your visual studio into debug or release mode?
– bradbury9
Nov 24 '18 at 19:07
How can a tree be an array (long tree)? Shouldn't a tree be a root Node? Each node would have a left and right. To get height you must transverse the Nodes and find the max number of nodes from root to leaves.
– jdweng
Nov 24 '18 at 20:44
@jdweng That looks like a flatenned tree, where the value of each element points to the index of its parent.
– NPras
Nov 25 '18 at 22:36
|
show 1 more comment
1
How to use your awesome Step Debugger
– Make StackOverflow Good Again
Nov 24 '18 at 18:37
@Disaffected1070452 for some reason , I can not debug
– lydal
Nov 24 '18 at 18:38
is your visual studio into debug or release mode?
– bradbury9
Nov 24 '18 at 19:07
How can a tree be an array (long tree)? Shouldn't a tree be a root Node? Each node would have a left and right. To get height you must transverse the Nodes and find the max number of nodes from root to leaves.
– jdweng
Nov 24 '18 at 20:44
@jdweng That looks like a flatenned tree, where the value of each element points to the index of its parent.
– NPras
Nov 25 '18 at 22:36
1
1
How to use your awesome Step Debugger
– Make StackOverflow Good Again
Nov 24 '18 at 18:37
How to use your awesome Step Debugger
– Make StackOverflow Good Again
Nov 24 '18 at 18:37
@Disaffected1070452 for some reason , I can not debug
– lydal
Nov 24 '18 at 18:38
@Disaffected1070452 for some reason , I can not debug
– lydal
Nov 24 '18 at 18:38
is your visual studio into debug or release mode?
– bradbury9
Nov 24 '18 at 19:07
is your visual studio into debug or release mode?
– bradbury9
Nov 24 '18 at 19:07
How can a tree be an array (long tree)? Shouldn't a tree be a root Node? Each node would have a left and right. To get height you must transverse the Nodes and find the max number of nodes from root to leaves.
– jdweng
Nov 24 '18 at 20:44
How can a tree be an array (long tree)? Shouldn't a tree be a root Node? Each node would have a left and right. To get height you must transverse the Nodes and find the max number of nodes from root to leaves.
– jdweng
Nov 24 '18 at 20:44
@jdweng That looks like a flatenned tree, where the value of each element points to the index of its parent.
– NPras
Nov 25 '18 at 22:36
@jdweng That looks like a flatenned tree, where the value of each element points to the index of its parent.
– NPras
Nov 25 '18 at 22:36
|
show 1 more comment
1 Answer
1
active
oldest
votes
0
You can swap the pointer direction of the tree nodes in O(n) when using 2 arrays (as pointer for the 2 children of the indexed node):
int size = 5;
int arr[size] = {4, -1, 4, 1, 1};
int a[size];
int b[size];
for (int i = 0; i < size; i++) {
a[i] = -1;
b[i] = -1;
} // I'm not c++ expert (I guess there are better way of init array with the same value...
int root = -1;
for (int i = 0; i < size; i++) {
if (arr[i] == -1)
root = i;
else if (a[arr[i]] != -1)
b[arr[i]] = i;
else
a[arr[i]] = i;
}
This is done in 1 for loop.
You can now use those 2 array to get you height is recursive way:
int findHeight(int current, int count, int a, int b) {
int maxV = count;
if (a[current] > -1)
maxV = max(findHeight(a[current], count + 1, a, b), maxV);
if (b[current] > -1)
maxV = max(findHeight(b[current], count + 1, a, b), maxV);
return maxV;
}
Execute this with:
int height = findHeight(root, 1, a, b); //(as root is the first level)
Total run time complexity is O(n)
Hope that help
answered Nov 26 '18 at 12:51
dWinderdWinder
5,63131129
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%2f53461187%2fcomputing-the-height-of-a-tree-c-sharp%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
0
You can swap the pointer direction of the tree nodes in O(n) when using 2 arrays (as pointer for the 2 children of the indexed node):
int size = 5;
int arr[size] = {4, -1, 4, 1, 1};
int a[size];
int b[size];
for (int i = 0; i < size; i++) {
a[i] = -1;
b[i] = -1;
} // I'm not c++ expert (I guess there are better way of init array with the same value...
int root = -1;
for (int i = 0; i < size; i++) {
if (arr[i] == -1)
root = i;
else if (a[arr[i]] != -1)
b[arr[i]] = i;
else
a[arr[i]] = i;
}
This is done in 1 for loop.
You can now use those 2 array to get you height is recursive way:
int findHeight(int current, int count, int a, int b) {
int maxV = count;
if (a[current] > -1)
maxV = max(findHeight(a[current], count + 1, a, b), maxV);
if (b[current] > -1)
maxV = max(findHeight(b[current], count + 1, a, b), maxV);
return maxV;
}
Execute this with:
int height = findHeight(root, 1, a, b); //(as root is the first level)
Total run time complexity is O(n)
Hope that help
answered Nov 26 '18 at 12:51
dWinderdWinder
5,63131129
add a comment |
0
You can swap the pointer direction of the tree nodes in O(n) when using 2 arrays (as pointer for the 2 children of the indexed node):
int size = 5;
int arr[size] = {4, -1, 4, 1, 1};
int a[size];
int b[size];
for (int i = 0; i < size; i++) {
a[i] = -1;
b[i] = -1;
} // I'm not c++ expert (I guess there are better way of init array with the same value...
int root = -1;
for (int i = 0; i < size; i++) {
if (arr[i] == -1)
root = i;
else if (a[arr[i]] != -1)
b[arr[i]] = i;
else
a[arr[i]] = i;
}
This is done in 1 for loop.
You can now use those 2 array to get you height is recursive way:
int findHeight(int current, int count, int a, int b) {
int maxV = count;
if (a[current] > -1)
maxV = max(findHeight(a[current], count + 1, a, b), maxV);
if (b[current] > -1)
maxV = max(findHeight(b[current], count + 1, a, b), maxV);
return maxV;
}
Execute this with:
int height = findHeight(root, 1, a, b); //(as root is the first level)
Total run time complexity is O(n)
Hope that help
answered Nov 26 '18 at 12:51
dWinderdWinder
5,63131129
add a comment |
0
0
0
You can swap the pointer direction of the tree nodes in O(n) when using 2 arrays (as pointer for the 2 children of the indexed node):
int size = 5;
int arr[size] = {4, -1, 4, 1, 1};
int a[size];
int b[size];
for (int i = 0; i < size; i++) {
a[i] = -1;
b[i] = -1;
} // I'm not c++ expert (I guess there are better way of init array with the same value...
int root = -1;
for (int i = 0; i < size; i++) {
if (arr[i] == -1)
root = i;
else if (a[arr[i]] != -1)
b[arr[i]] = i;
else
a[arr[i]] = i;
}
This is done in 1 for loop.
You can now use those 2 array to get you height is recursive way:
int findHeight(int current, int count, int a, int b) {
int maxV = count;
if (a[current] > -1)
maxV = max(findHeight(a[current], count + 1, a, b), maxV);
if (b[current] > -1)
maxV = max(findHeight(b[current], count + 1, a, b), maxV);
return maxV;
}
Execute this with:
int height = findHeight(root, 1, a, b); //(as root is the first level)
Total run time complexity is O(n)
Hope that help
answered Nov 26 '18 at 12:51
dWinderdWinder
5,63131129
You can swap the pointer direction of the tree nodes in O(n) when using 2 arrays (as pointer for the 2 children of the indexed node):
int size = 5;
int arr[size] = {4, -1, 4, 1, 1};
int a[size];
int b[size];
for (int i = 0; i < size; i++) {
a[i] = -1;
b[i] = -1;
} // I'm not c++ expert (I guess there are better way of init array with the same value...
int root = -1;
for (int i = 0; i < size; i++) {
if (arr[i] == -1)
root = i;
else if (a[arr[i]] != -1)
b[arr[i]] = i;
else
a[arr[i]] = i;
}
This is done in 1 for loop.
You can now use those 2 array to get you height is recursive way:
int findHeight(int current, int count, int a, int b) {
int maxV = count;
if (a[current] > -1)
maxV = max(findHeight(a[current], count + 1, a, b), maxV);
if (b[current] > -1)
maxV = max(findHeight(b[current], count + 1, a, b), maxV);
return maxV;
}
Execute this with:
int height = findHeight(root, 1, a, b); //(as root is the first level)
Total run time complexity is O(n)
Hope that help
answered Nov 26 '18 at 12:51
dWinderdWinder
5,63131129
edited Nov 26 '18 at 13:16
answered Nov 26 '18 at 12:51
dWinderdWinder
5,63131129
answered Nov 26 '18 at 12:51
dWinderdWinder
5,63131129
answered Nov 26 '18 at 12:51
dWinderdWinder
5,63131129
5,63131129
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%2f53461187%2fcomputing-the-height-of-a-tree-c-sharp%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
How to use your awesome Step Debugger
– Make StackOverflow Good Again
Nov 24 '18 at 18:37
@Disaffected1070452 for some reason , I can not debug
– lydal
Nov 24 '18 at 18:38
is your visual studio into debug or release mode?
– bradbury9
Nov 24 '18 at 19:07
How can a tree be an array (long tree)? Shouldn't a tree be a root Node? Each node would have a left and right. To get height you must transverse the Nodes and find the max number of nodes from root to leaves.
– jdweng
Nov 24 '18 at 20:44
@jdweng That looks like a flatenned tree, where the value of each element points to the index of its parent.
– NPras
Nov 25 '18 at 22:36