Confusion in terminology while defining Balanced Binary Tree: Height of a subtree vs. Height of a node
Referencing the answer to this question
A balanced binary tree is:
- The left and right subtrees' heights differ by at most one, AND
- The left subtree is balanced, AND
- The right subtree is balanced
Now, using the same example
A
/
B C
/ /
D E F
/
G
The tree is rooted at A.
Now, when looking at the definition for height balanced tree, the first point says:
The left and right subtrees' heights differ by at most one
If I am currently at the node A, to determine the height of the LEFT SUBTREE of A I am confused if I calculate:
- Height of node A looking at the deepest left child from A (D) OR
- Height of node B looking at the deepest left child from A (by extension B) (D)
If I am currently at the node A, to determine the height of the RIGHT SUBTREE of A I am confused if I calculate:
- Height of node A looking at the deepest right child from A (F) OR
- Height of node C looking at the deepest right child from A (by extension C) (F)
data-structures tree binary-tree tree-traversal recursive-datastructures
asked Nov 15 '18 at 19:47
AbhishekAbhishek
1,058221
add a comment |
Referencing the answer to this question
A balanced binary tree is:
- The left and right subtrees' heights differ by at most one, AND
- The left subtree is balanced, AND
- The right subtree is balanced
Now, using the same example
A
/
B C
/ /
D E F
/
G
The tree is rooted at A.
Now, when looking at the definition for height balanced tree, the first point says:
The left and right subtrees' heights differ by at most one
If I am currently at the node A, to determine the height of the LEFT SUBTREE of A I am confused if I calculate:
- Height of node A looking at the deepest left child from A (D) OR
- Height of node B looking at the deepest left child from A (by extension B) (D)
If I am currently at the node A, to determine the height of the RIGHT SUBTREE of A I am confused if I calculate:
- Height of node A looking at the deepest right child from A (F) OR
- Height of node C looking at the deepest right child from A (by extension C) (F)
data-structures tree binary-tree tree-traversal recursive-datastructures
asked Nov 15 '18 at 19:47
AbhishekAbhishek
1,058221
add a comment |
Referencing the answer to this question
A balanced binary tree is:
- The left and right subtrees' heights differ by at most one, AND
- The left subtree is balanced, AND
- The right subtree is balanced
Now, using the same example
A
/
B C
/ /
D E F
/
G
The tree is rooted at A.
Now, when looking at the definition for height balanced tree, the first point says:
The left and right subtrees' heights differ by at most one
If I am currently at the node A, to determine the height of the LEFT SUBTREE of A I am confused if I calculate:
- Height of node A looking at the deepest left child from A (D) OR
- Height of node B looking at the deepest left child from A (by extension B) (D)
If I am currently at the node A, to determine the height of the RIGHT SUBTREE of A I am confused if I calculate:
- Height of node A looking at the deepest right child from A (F) OR
- Height of node C looking at the deepest right child from A (by extension C) (F)
data-structures tree binary-tree tree-traversal recursive-datastructures
asked Nov 15 '18 at 19:47
AbhishekAbhishek
1,058221
Referencing the answer to this question
A balanced binary tree is:
- The left and right subtrees' heights differ by at most one, AND
- The left subtree is balanced, AND
- The right subtree is balanced
Now, using the same example
A
/
B C
/ /
D E F
/
G
The tree is rooted at A.
Now, when looking at the definition for height balanced tree, the first point says:
The left and right subtrees' heights differ by at most one
If I am currently at the node A, to determine the height of the LEFT SUBTREE of A I am confused if I calculate:
- Height of node A looking at the deepest left child from A (D) OR
- Height of node B looking at the deepest left child from A (by extension B) (D)
If I am currently at the node A, to determine the height of the RIGHT SUBTREE of A I am confused if I calculate:
- Height of node A looking at the deepest right child from A (F) OR
- Height of node C looking at the deepest right child from A (by extension C) (F)
data-structures tree binary-tree tree-traversal recursive-datastructures
data-structures tree binary-tree tree-traversal recursive-datastructures
asked Nov 15 '18 at 19:47
AbhishekAbhishek
1,058221
asked Nov 15 '18 at 19:47
AbhishekAbhishek
1,058221
asked Nov 15 '18 at 19:47
AbhishekAbhishek
1,058221
asked Nov 15 '18 at 19:47
AbhishekAbhishek
1,058221
asked Nov 15 '18 at 19:47
AbhishekAbhishek
1,058221
1,058221
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
'The height of a subtree' is generally translated as 'height of the root of the subtree'. Bumped into this explanation while listening to this MIT OpenCourseWare lecture, at timestamp 13:17.
answered Nov 17 '18 at 14:35
AbhishekAbhishek
1,058221
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%2f53326910%2fconfusion-in-terminology-while-defining-balanced-binary-tree-height-of-a-subtre%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
'The height of a subtree' is generally translated as 'height of the root of the subtree'. Bumped into this explanation while listening to this MIT OpenCourseWare lecture, at timestamp 13:17.
answered Nov 17 '18 at 14:35
AbhishekAbhishek
1,058221
add a comment |
'The height of a subtree' is generally translated as 'height of the root of the subtree'. Bumped into this explanation while listening to this MIT OpenCourseWare lecture, at timestamp 13:17.
answered Nov 17 '18 at 14:35
AbhishekAbhishek
1,058221
add a comment |
'The height of a subtree' is generally translated as 'height of the root of the subtree'. Bumped into this explanation while listening to this MIT OpenCourseWare lecture, at timestamp 13:17.
answered Nov 17 '18 at 14:35
AbhishekAbhishek
1,058221
'The height of a subtree' is generally translated as 'height of the root of the subtree'. Bumped into this explanation while listening to this MIT OpenCourseWare lecture, at timestamp 13:17.
answered Nov 17 '18 at 14:35
AbhishekAbhishek
1,058221
answered Nov 17 '18 at 14:35
AbhishekAbhishek
1,058221
answered Nov 17 '18 at 14:35
AbhishekAbhishek
1,058221
answered Nov 17 '18 at 14:35
AbhishekAbhishek
1,058221
1,058221
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%2f53326910%2fconfusion-in-terminology-while-defining-balanced-binary-tree-height-of-a-subtre%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
