Recursion in binary trees to return a bool value?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
I want to create a recursive function that takes a binary tree as its parameter and returns True if every leaf below a node is greater than its parent. If just one node fails to meet this condition, the entire function should return False.
However, I am struggling to come up with a base case, as well as fully understanding how to stop the function and return False if even just one part of the tree does not meet the condition. Any help would be greatly appreciated.
python recursion binary-tree
asked Nov 24 '18 at 23:23
B. NguyenB. Nguyen
83
add a comment |
I want to create a recursive function that takes a binary tree as its parameter and returns True if every leaf below a node is greater than its parent. If just one node fails to meet this condition, the entire function should return False.
However, I am struggling to come up with a base case, as well as fully understanding how to stop the function and return False if even just one part of the tree does not meet the condition. Any help would be greatly appreciated.
python recursion binary-tree
asked Nov 24 '18 at 23:23
B. NguyenB. Nguyen
83
1
In Pythonandis short-cutting and hence naturally "stops" the function. Hence you can justandthe condition for the two leafs of each node.
– a_guest
Nov 24 '18 at 23:31
add a comment |
I want to create a recursive function that takes a binary tree as its parameter and returns True if every leaf below a node is greater than its parent. If just one node fails to meet this condition, the entire function should return False.
However, I am struggling to come up with a base case, as well as fully understanding how to stop the function and return False if even just one part of the tree does not meet the condition. Any help would be greatly appreciated.
python recursion binary-tree
asked Nov 24 '18 at 23:23
B. NguyenB. Nguyen
83
I want to create a recursive function that takes a binary tree as its parameter and returns True if every leaf below a node is greater than its parent. If just one node fails to meet this condition, the entire function should return False.
However, I am struggling to come up with a base case, as well as fully understanding how to stop the function and return False if even just one part of the tree does not meet the condition. Any help would be greatly appreciated.
python recursion binary-tree
python recursion binary-tree
asked Nov 24 '18 at 23:23
B. NguyenB. Nguyen
83
asked Nov 24 '18 at 23:23
B. NguyenB. Nguyen
83
asked Nov 24 '18 at 23:23
B. NguyenB. Nguyen
83
asked Nov 24 '18 at 23:23
B. NguyenB. Nguyen
83
asked Nov 24 '18 at 23:23
B. NguyenB. Nguyen
83
83
1
In Pythonandis short-cutting and hence naturally "stops" the function. Hence you can justandthe condition for the two leafs of each node.
– a_guest
Nov 24 '18 at 23:31
add a comment |
1
In Pythonandis short-cutting and hence naturally "stops" the function. Hence you can justandthe condition for the two leafs of each node.
– a_guest
Nov 24 '18 at 23:31
1
1
In Python
and is short-cutting and hence naturally "stops" the function. Hence you can just and the condition for the two leafs of each node.– a_guest
Nov 24 '18 at 23:31
In Python
and is short-cutting and hence naturally "stops" the function. Hence you can just and the condition for the two leafs of each node.– a_guest
Nov 24 '18 at 23:31
add a comment |
2 Answers
2
active
oldest
votes
When recurring through the tree, the base case would be a leaf node - that is, a node with no children. For such a node, you would assume that it has met the test (since otherwise, you algorithm should have already returned false), so you would return true.
For the general case, you would want to check if the node is smaller than both it’s children, and if not, return False. Otherwise, to ensure that the condition holds for both children, you would return the result of recurring down the left side and the result of recurring down the right:
return check(node.left) and check(node.right)
answered Nov 24 '18 at 23:36
GniemGniem
914
add a comment |
Using recursion, something like this should work:
def children_gt_parent(node, parent_val):
if node is None:
return True
if node.value <= parent_val:
return False
return children_gt_parent(node.left, node.value) and children_gt_parent(node.right, node.value)
You then call it like:
tf = children_gt_parent(root, root.value)
answered Nov 24 '18 at 23:40
mnisticmnistic
7,24611025
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%2f53463266%2frecursion-in-binary-trees-to-return-a-bool-value%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
When recurring through the tree, the base case would be a leaf node - that is, a node with no children. For such a node, you would assume that it has met the test (since otherwise, you algorithm should have already returned false), so you would return true.
For the general case, you would want to check if the node is smaller than both it’s children, and if not, return False. Otherwise, to ensure that the condition holds for both children, you would return the result of recurring down the left side and the result of recurring down the right:
return check(node.left) and check(node.right)
answered Nov 24 '18 at 23:36
GniemGniem
914
add a comment |
When recurring through the tree, the base case would be a leaf node - that is, a node with no children. For such a node, you would assume that it has met the test (since otherwise, you algorithm should have already returned false), so you would return true.
For the general case, you would want to check if the node is smaller than both it’s children, and if not, return False. Otherwise, to ensure that the condition holds for both children, you would return the result of recurring down the left side and the result of recurring down the right:
return check(node.left) and check(node.right)
answered Nov 24 '18 at 23:36
GniemGniem
914
add a comment |
When recurring through the tree, the base case would be a leaf node - that is, a node with no children. For such a node, you would assume that it has met the test (since otherwise, you algorithm should have already returned false), so you would return true.
For the general case, you would want to check if the node is smaller than both it’s children, and if not, return False. Otherwise, to ensure that the condition holds for both children, you would return the result of recurring down the left side and the result of recurring down the right:
return check(node.left) and check(node.right)
answered Nov 24 '18 at 23:36
GniemGniem
914
When recurring through the tree, the base case would be a leaf node - that is, a node with no children. For such a node, you would assume that it has met the test (since otherwise, you algorithm should have already returned false), so you would return true.
For the general case, you would want to check if the node is smaller than both it’s children, and if not, return False. Otherwise, to ensure that the condition holds for both children, you would return the result of recurring down the left side and the result of recurring down the right:
return check(node.left) and check(node.right)
answered Nov 24 '18 at 23:36
GniemGniem
914
answered Nov 24 '18 at 23:36
GniemGniem
914
answered Nov 24 '18 at 23:36
GniemGniem
914
answered Nov 24 '18 at 23:36
GniemGniem
914
914
add a comment |
add a comment |
Using recursion, something like this should work:
def children_gt_parent(node, parent_val):
if node is None:
return True
if node.value <= parent_val:
return False
return children_gt_parent(node.left, node.value) and children_gt_parent(node.right, node.value)
You then call it like:
tf = children_gt_parent(root, root.value)
answered Nov 24 '18 at 23:40
mnisticmnistic
7,24611025
add a comment |
Using recursion, something like this should work:
def children_gt_parent(node, parent_val):
if node is None:
return True
if node.value <= parent_val:
return False
return children_gt_parent(node.left, node.value) and children_gt_parent(node.right, node.value)
You then call it like:
tf = children_gt_parent(root, root.value)
answered Nov 24 '18 at 23:40
mnisticmnistic
7,24611025
add a comment |
Using recursion, something like this should work:
def children_gt_parent(node, parent_val):
if node is None:
return True
if node.value <= parent_val:
return False
return children_gt_parent(node.left, node.value) and children_gt_parent(node.right, node.value)
You then call it like:
tf = children_gt_parent(root, root.value)
answered Nov 24 '18 at 23:40
mnisticmnistic
7,24611025
Using recursion, something like this should work:
def children_gt_parent(node, parent_val):
if node is None:
return True
if node.value <= parent_val:
return False
return children_gt_parent(node.left, node.value) and children_gt_parent(node.right, node.value)
You then call it like:
tf = children_gt_parent(root, root.value)
answered Nov 24 '18 at 23:40
mnisticmnistic
7,24611025
answered Nov 24 '18 at 23:40
mnisticmnistic
7,24611025
answered Nov 24 '18 at 23:40
mnisticmnistic
7,24611025
answered Nov 24 '18 at 23:40
mnisticmnistic
7,24611025
7,24611025
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%2f53463266%2frecursion-in-binary-trees-to-return-a-bool-value%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
In Python
andis short-cutting and hence naturally "stops" the function. Hence you can justandthe condition for the two leafs of each node.– a_guest
Nov 24 '18 at 23:31