max height of binary search tree
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
so I need to find the max height of a binary tree but for some reason the result of the code provided below is off by 1.
For example if the max height is 3 the following code will give me 2.
if the max height is 4 the result will be 3.
I am not sure why? the root is not considered for the calculations of the max height therefore i set leftCounter and rightCounter to be 0.
any ideas?
public int getMaxHeight(BST.TreeNode<E> n) {
if(n == null) {
return 0;
}
int leftCounter = 0;
int rightCounter = 0;
if(n.left != null) {
leftCounter = getMaxHeight(n.left) +1 ;
}
if(n.right != null) {
rightCounter = getMaxHeight(n.right) +1 ;
}
if(leftCounter > rightCounter) {
return leftCounter;
}
else
return rightCounter;
}
the max height of this binary tree should be 3:
because of the elements 5,9,11. the root is not counted for the max
height.
15
_____|____
10 21
___|___ __|__
9 14 16 24
|__
25
java
asked Nov 24 '18 at 12:39
peter-cspeter-cs
338
add a comment |
so I need to find the max height of a binary tree but for some reason the result of the code provided below is off by 1.
For example if the max height is 3 the following code will give me 2.
if the max height is 4 the result will be 3.
I am not sure why? the root is not considered for the calculations of the max height therefore i set leftCounter and rightCounter to be 0.
any ideas?
public int getMaxHeight(BST.TreeNode<E> n) {
if(n == null) {
return 0;
}
int leftCounter = 0;
int rightCounter = 0;
if(n.left != null) {
leftCounter = getMaxHeight(n.left) +1 ;
}
if(n.right != null) {
rightCounter = getMaxHeight(n.right) +1 ;
}
if(leftCounter > rightCounter) {
return leftCounter;
}
else
return rightCounter;
}
the max height of this binary tree should be 3:
because of the elements 5,9,11. the root is not counted for the max
height.
15
_____|____
10 21
___|___ __|__
9 14 16 24
|__
25
java
asked Nov 24 '18 at 12:39
peter-cspeter-cs
338
It looks like you may need to learn to use a debugger. Please help yourself to some complementary debugging techniques. If you still have issues afterwards, please edit your question to be more specific with what help you need.
– Joe C
Nov 24 '18 at 12:39
Please edit your question to include a sample binary tree and specify the max height it should have and why it should be that number (and not one number above or below it).
– Progman
Nov 24 '18 at 13:15
1
Because you're not considering therootnode just return1+Max(....
– suvojit_007
Nov 24 '18 at 13:21
add a comment |
so I need to find the max height of a binary tree but for some reason the result of the code provided below is off by 1.
For example if the max height is 3 the following code will give me 2.
if the max height is 4 the result will be 3.
I am not sure why? the root is not considered for the calculations of the max height therefore i set leftCounter and rightCounter to be 0.
any ideas?
public int getMaxHeight(BST.TreeNode<E> n) {
if(n == null) {
return 0;
}
int leftCounter = 0;
int rightCounter = 0;
if(n.left != null) {
leftCounter = getMaxHeight(n.left) +1 ;
}
if(n.right != null) {
rightCounter = getMaxHeight(n.right) +1 ;
}
if(leftCounter > rightCounter) {
return leftCounter;
}
else
return rightCounter;
}
the max height of this binary tree should be 3:
because of the elements 5,9,11. the root is not counted for the max
height.
15
_____|____
10 21
___|___ __|__
9 14 16 24
|__
25
java
asked Nov 24 '18 at 12:39
peter-cspeter-cs
338
so I need to find the max height of a binary tree but for some reason the result of the code provided below is off by 1.
For example if the max height is 3 the following code will give me 2.
if the max height is 4 the result will be 3.
I am not sure why? the root is not considered for the calculations of the max height therefore i set leftCounter and rightCounter to be 0.
any ideas?
public int getMaxHeight(BST.TreeNode<E> n) {
if(n == null) {
return 0;
}
int leftCounter = 0;
int rightCounter = 0;
if(n.left != null) {
leftCounter = getMaxHeight(n.left) +1 ;
}
if(n.right != null) {
rightCounter = getMaxHeight(n.right) +1 ;
}
if(leftCounter > rightCounter) {
return leftCounter;
}
else
return rightCounter;
}
the max height of this binary tree should be 3:
because of the elements 5,9,11. the root is not counted for the max
height.
15
_____|____
10 21
___|___ __|__
9 14 16 24
|__
25
java
java
asked Nov 24 '18 at 12:39
peter-cspeter-cs
338
asked Nov 24 '18 at 12:39
peter-cspeter-cs
338
edited Nov 28 '18 at 0:46
peter-cs
asked Nov 24 '18 at 12:39
peter-cspeter-cs
338
asked Nov 24 '18 at 12:39
peter-cspeter-cs
338
asked Nov 24 '18 at 12:39
peter-cspeter-cs
338
338
It looks like you may need to learn to use a debugger. Please help yourself to some complementary debugging techniques. If you still have issues afterwards, please edit your question to be more specific with what help you need.
– Joe C
Nov 24 '18 at 12:39
Please edit your question to include a sample binary tree and specify the max height it should have and why it should be that number (and not one number above or below it).
– Progman
Nov 24 '18 at 13:15
1
Because you're not considering therootnode just return1+Max(....
– suvojit_007
Nov 24 '18 at 13:21
add a comment |
It looks like you may need to learn to use a debugger. Please help yourself to some complementary debugging techniques. If you still have issues afterwards, please edit your question to be more specific with what help you need.
– Joe C
Nov 24 '18 at 12:39
Please edit your question to include a sample binary tree and specify the max height it should have and why it should be that number (and not one number above or below it).
– Progman
Nov 24 '18 at 13:15
1
Because you're not considering therootnode just return1+Max(....
– suvojit_007
Nov 24 '18 at 13:21
It looks like you may need to learn to use a debugger. Please help yourself to some complementary debugging techniques. If you still have issues afterwards, please edit your question to be more specific with what help you need.
– Joe C
Nov 24 '18 at 12:39
It looks like you may need to learn to use a debugger. Please help yourself to some complementary debugging techniques. If you still have issues afterwards, please edit your question to be more specific with what help you need.
– Joe C
Nov 24 '18 at 12:39
Please edit your question to include a sample binary tree and specify the max height it should have and why it should be that number (and not one number above or below it).
– Progman
Nov 24 '18 at 13:15
Please edit your question to include a sample binary tree and specify the max height it should have and why it should be that number (and not one number above or below it).
– Progman
Nov 24 '18 at 13:15
1
1
Because you're not considering the
root node just return 1+Max(....– suvojit_007
Nov 24 '18 at 13:21
Because you're not considering the
root node just return 1+Max(....– suvojit_007
Nov 24 '18 at 13:21
add a comment |
2 Answers
2
active
oldest
votes
Your code actually returns the correct value; it's just that you misunderstand what the height of a tree means. The height is the number of edges on the longest path from root to leaf, not the number of nodes on the path. So the following tree
3
_____|____
4 5
___|___ __|__
6 7 8 9
has a height of 2, not 3. What you are looking for is the number of levels in the tree, not the height.
public int getNumberOfLevels(BST.TreeNode<E> n) {
if(n == null) return 0;
int left = getNumberOfLevels(n.left);
int right = getNumberOfLevels(n.right);
return 1 + Math.max(left, right);
}
answered Nov 24 '18 at 13:16
Leo AsoLeo Aso
5,57711229
add a comment |
you can initialize leftCounter, and RightCounter by 1. Reason being if(n==null) -> false
which means height is atleast 1
answered Nov 24 '18 at 12:43
Jigar WalaJigar Wala
666
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
});
}
});
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%2f53458227%2fmax-height-of-binary-search-tree%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
Your code actually returns the correct value; it's just that you misunderstand what the height of a tree means. The height is the number of edges on the longest path from root to leaf, not the number of nodes on the path. So the following tree
3
_____|____
4 5
___|___ __|__
6 7 8 9
has a height of 2, not 3. What you are looking for is the number of levels in the tree, not the height.
public int getNumberOfLevels(BST.TreeNode<E> n) {
if(n == null) return 0;
int left = getNumberOfLevels(n.left);
int right = getNumberOfLevels(n.right);
return 1 + Math.max(left, right);
}
answered Nov 24 '18 at 13:16
Leo AsoLeo Aso
5,57711229
add a comment |
Your code actually returns the correct value; it's just that you misunderstand what the height of a tree means. The height is the number of edges on the longest path from root to leaf, not the number of nodes on the path. So the following tree
3
_____|____
4 5
___|___ __|__
6 7 8 9
has a height of 2, not 3. What you are looking for is the number of levels in the tree, not the height.
public int getNumberOfLevels(BST.TreeNode<E> n) {
if(n == null) return 0;
int left = getNumberOfLevels(n.left);
int right = getNumberOfLevels(n.right);
return 1 + Math.max(left, right);
}
answered Nov 24 '18 at 13:16
Leo AsoLeo Aso
5,57711229
add a comment |
Your code actually returns the correct value; it's just that you misunderstand what the height of a tree means. The height is the number of edges on the longest path from root to leaf, not the number of nodes on the path. So the following tree
3
_____|____
4 5
___|___ __|__
6 7 8 9
has a height of 2, not 3. What you are looking for is the number of levels in the tree, not the height.
public int getNumberOfLevels(BST.TreeNode<E> n) {
if(n == null) return 0;
int left = getNumberOfLevels(n.left);
int right = getNumberOfLevels(n.right);
return 1 + Math.max(left, right);
}
answered Nov 24 '18 at 13:16
Leo AsoLeo Aso
5,57711229
Your code actually returns the correct value; it's just that you misunderstand what the height of a tree means. The height is the number of edges on the longest path from root to leaf, not the number of nodes on the path. So the following tree
3
_____|____
4 5
___|___ __|__
6 7 8 9
has a height of 2, not 3. What you are looking for is the number of levels in the tree, not the height.
public int getNumberOfLevels(BST.TreeNode<E> n) {
if(n == null) return 0;
int left = getNumberOfLevels(n.left);
int right = getNumberOfLevels(n.right);
return 1 + Math.max(left, right);
}
answered Nov 24 '18 at 13:16
Leo AsoLeo Aso
5,57711229
answered Nov 24 '18 at 13:16
Leo AsoLeo Aso
5,57711229
answered Nov 24 '18 at 13:16
Leo AsoLeo Aso
5,57711229
answered Nov 24 '18 at 13:16
Leo AsoLeo Aso
5,57711229
5,57711229
add a comment |
add a comment |
you can initialize leftCounter, and RightCounter by 1. Reason being if(n==null) -> false
which means height is atleast 1
answered Nov 24 '18 at 12:43
Jigar WalaJigar Wala
666
add a comment |
you can initialize leftCounter, and RightCounter by 1. Reason being if(n==null) -> false
which means height is atleast 1
answered Nov 24 '18 at 12:43
Jigar WalaJigar Wala
666
add a comment |
you can initialize leftCounter, and RightCounter by 1. Reason being if(n==null) -> false
which means height is atleast 1
answered Nov 24 '18 at 12:43
Jigar WalaJigar Wala
666
you can initialize leftCounter, and RightCounter by 1. Reason being if(n==null) -> false
which means height is atleast 1
answered Nov 24 '18 at 12:43
Jigar WalaJigar Wala
666
answered Nov 24 '18 at 12:43
Jigar WalaJigar Wala
666
answered Nov 24 '18 at 12:43
Jigar WalaJigar Wala
666
answered Nov 24 '18 at 12:43
Jigar WalaJigar Wala
666
666
add a comment |
add a 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%2f53458227%2fmax-height-of-binary-search-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
It looks like you may need to learn to use a debugger. Please help yourself to some complementary debugging techniques. If you still have issues afterwards, please edit your question to be more specific with what help you need.
– Joe C
Nov 24 '18 at 12:39
Please edit your question to include a sample binary tree and specify the max height it should have and why it should be that number (and not one number above or below it).
– Progman
Nov 24 '18 at 13:15
1
Because you're not considering the
rootnode just return1+Max(....– suvojit_007
Nov 24 '18 at 13:21