Binary Search Tree find successor of given key (where the key does not have to be in tree)
0
How would I change the following code I have written to account for an inputed pair k that is not in the bst? In other words, how would I find the successor of a key in a binary search tree that does not exist in it?
public Record getSuccessor(Pair k, Node root) {
if(root == null) {
return null;
}
if(k.compareTo(root.getNodeRecord().getKey()) == 0) {
if(root.getRightChild() != null) {
return getSmallest(root.getRightChild());
}
else {
return root.getParent().getNodeRecord();
}
}
else {
Record left = getSuccessor(k, root.getLeftChild());
if(left != null) {
return left;
}
return getSuccessor(k, root.getRightChild());
}
}
search tree binary
edited Nov 12 '18 at 2:46
Gene
37.5k44274
asked Nov 12 '18 at 0:48
Ben Tilden
496
add a comment |
0
How would I change the following code I have written to account for an inputed pair k that is not in the bst? In other words, how would I find the successor of a key in a binary search tree that does not exist in it?
public Record getSuccessor(Pair k, Node root) {
if(root == null) {
return null;
}
if(k.compareTo(root.getNodeRecord().getKey()) == 0) {
if(root.getRightChild() != null) {
return getSmallest(root.getRightChild());
}
else {
return root.getParent().getNodeRecord();
}
}
else {
Record left = getSuccessor(k, root.getLeftChild());
if(left != null) {
return left;
}
return getSuccessor(k, root.getRightChild());
}
}
search tree binary
edited Nov 12 '18 at 2:46
Gene
37.5k44274
asked Nov 12 '18 at 0:48
Ben Tilden
496
could you give an example? for instance, what if the key is2and you have2,4,5,6,8in BST. which value do you imply bysuccessor not in bst? by the way there is a mismatch between the title of your question (predecessor) and question itself (successor)
– mangusta
Nov 12 '18 at 1:58
@mangusta for example, if the key is 5 and we have 8, 3, 1, 6, 4, 7 ,10, 14 and 3 is BST, the successor to 5 (although 5 is not in the BST) would be 6
– Ben Tilden
Nov 12 '18 at 2:41
have you tried in-order DFS traversal? it is going to give you all bst elements in increasing order so that you may find the successor of any key in linear time
– mangusta
Nov 12 '18 at 3:05
1
ah, seems that the traversal is not necessary at all. you simply save the current node everytime before going left, and then there are several possible cases: 1. you reached the key but it doesn't have a right child. then successor is the key you saved on going left last time. 2. you reached the key and it has a right child, then you move right and then continuously move left until you reach leaf node. 3. the key is not in tree. then you end up with some leaf node and its successor is the key you saved on going left last time
– mangusta
Nov 12 '18 at 3:40
add a comment |
0
0
0
How would I change the following code I have written to account for an inputed pair k that is not in the bst? In other words, how would I find the successor of a key in a binary search tree that does not exist in it?
public Record getSuccessor(Pair k, Node root) {
if(root == null) {
return null;
}
if(k.compareTo(root.getNodeRecord().getKey()) == 0) {
if(root.getRightChild() != null) {
return getSmallest(root.getRightChild());
}
else {
return root.getParent().getNodeRecord();
}
}
else {
Record left = getSuccessor(k, root.getLeftChild());
if(left != null) {
return left;
}
return getSuccessor(k, root.getRightChild());
}
}
search tree binary
edited Nov 12 '18 at 2:46
Gene
37.5k44274
asked Nov 12 '18 at 0:48
Ben Tilden
496
How would I change the following code I have written to account for an inputed pair k that is not in the bst? In other words, how would I find the successor of a key in a binary search tree that does not exist in it?
public Record getSuccessor(Pair k, Node root) {
if(root == null) {
return null;
}
if(k.compareTo(root.getNodeRecord().getKey()) == 0) {
if(root.getRightChild() != null) {
return getSmallest(root.getRightChild());
}
else {
return root.getParent().getNodeRecord();
}
}
else {
Record left = getSuccessor(k, root.getLeftChild());
if(left != null) {
return left;
}
return getSuccessor(k, root.getRightChild());
}
}
search tree binary
search tree binary
edited Nov 12 '18 at 2:46
Gene
37.5k44274
asked Nov 12 '18 at 0:48
Ben Tilden
496
edited Nov 12 '18 at 2:46
Gene
37.5k44274
asked Nov 12 '18 at 0:48
Ben Tilden
496
edited Nov 12 '18 at 2:46
Gene
37.5k44274
edited Nov 12 '18 at 2:46
Gene
37.5k44274
edited Nov 12 '18 at 2:46
Gene
37.5k44274
37.5k44274
asked Nov 12 '18 at 0:48
Ben Tilden
496
asked Nov 12 '18 at 0:48
Ben Tilden
496
asked Nov 12 '18 at 0:48
Ben Tilden
496
496
could you give an example? for instance, what if the key is2and you have2,4,5,6,8in BST. which value do you imply bysuccessor not in bst? by the way there is a mismatch between the title of your question (predecessor) and question itself (successor)
– mangusta
Nov 12 '18 at 1:58
@mangusta for example, if the key is 5 and we have 8, 3, 1, 6, 4, 7 ,10, 14 and 3 is BST, the successor to 5 (although 5 is not in the BST) would be 6
– Ben Tilden
Nov 12 '18 at 2:41
have you tried in-order DFS traversal? it is going to give you all bst elements in increasing order so that you may find the successor of any key in linear time
– mangusta
Nov 12 '18 at 3:05
1
ah, seems that the traversal is not necessary at all. you simply save the current node everytime before going left, and then there are several possible cases: 1. you reached the key but it doesn't have a right child. then successor is the key you saved on going left last time. 2. you reached the key and it has a right child, then you move right and then continuously move left until you reach leaf node. 3. the key is not in tree. then you end up with some leaf node and its successor is the key you saved on going left last time
– mangusta
Nov 12 '18 at 3:40
add a comment |
could you give an example? for instance, what if the key is2and you have2,4,5,6,8in BST. which value do you imply bysuccessor not in bst? by the way there is a mismatch between the title of your question (predecessor) and question itself (successor)
– mangusta
Nov 12 '18 at 1:58
@mangusta for example, if the key is 5 and we have 8, 3, 1, 6, 4, 7 ,10, 14 and 3 is BST, the successor to 5 (although 5 is not in the BST) would be 6
– Ben Tilden
Nov 12 '18 at 2:41
have you tried in-order DFS traversal? it is going to give you all bst elements in increasing order so that you may find the successor of any key in linear time
– mangusta
Nov 12 '18 at 3:05
1
ah, seems that the traversal is not necessary at all. you simply save the current node everytime before going left, and then there are several possible cases: 1. you reached the key but it doesn't have a right child. then successor is the key you saved on going left last time. 2. you reached the key and it has a right child, then you move right and then continuously move left until you reach leaf node. 3. the key is not in tree. then you end up with some leaf node and its successor is the key you saved on going left last time
– mangusta
Nov 12 '18 at 3:40
could you give an example? for instance, what if the key is
2 and you have 2, 4, 5, 6, 8 in BST. which value do you imply by successor not in bst? by the way there is a mismatch between the title of your question (predecessor) and question itself (successor)– mangusta
Nov 12 '18 at 1:58
could you give an example? for instance, what if the key is
2 and you have 2, 4, 5, 6, 8 in BST. which value do you imply by successor not in bst? by the way there is a mismatch between the title of your question (predecessor) and question itself (successor)– mangusta
Nov 12 '18 at 1:58
@mangusta for example, if the key is 5 and we have 8, 3, 1, 6, 4, 7 ,10, 14 and 3 is BST, the successor to 5 (although 5 is not in the BST) would be 6
– Ben Tilden
Nov 12 '18 at 2:41
@mangusta for example, if the key is 5 and we have 8, 3, 1, 6, 4, 7 ,10, 14 and 3 is BST, the successor to 5 (although 5 is not in the BST) would be 6
– Ben Tilden
Nov 12 '18 at 2:41
have you tried in-order DFS traversal? it is going to give you all bst elements in increasing order so that you may find the successor of any key in linear time
– mangusta
Nov 12 '18 at 3:05
have you tried in-order DFS traversal? it is going to give you all bst elements in increasing order so that you may find the successor of any key in linear time
– mangusta
Nov 12 '18 at 3:05
1
1
ah, seems that the traversal is not necessary at all. you simply save the current node everytime before going left, and then there are several possible cases: 1. you reached the key but it doesn't have a right child. then successor is the key you saved on going left last time. 2. you reached the key and it has a right child, then you move right and then continuously move left until you reach leaf node. 3. the key is not in tree. then you end up with some leaf node and its successor is the key you saved on going left last time
– mangusta
Nov 12 '18 at 3:40
ah, seems that the traversal is not necessary at all. you simply save the current node everytime before going left, and then there are several possible cases: 1. you reached the key but it doesn't have a right child. then successor is the key you saved on going left last time. 2. you reached the key and it has a right child, then you move right and then continuously move left until you reach leaf node. 3. the key is not in tree. then you end up with some leaf node and its successor is the key you saved on going left last time
– mangusta
Nov 12 '18 at 3:40
add a comment |
active
oldest
votes
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%2f53254725%2fbinary-search-tree-find-successor-of-given-key-where-the-key-does-not-have-to-b%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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%2f53254725%2fbinary-search-tree-find-successor-of-given-key-where-the-key-does-not-have-to-b%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
could you give an example? for instance, what if the key is
2and you have2,4,5,6,8in BST. which value do you imply bysuccessor not in bst? by the way there is a mismatch between the title of your question (predecessor) and question itself (successor)– mangusta
Nov 12 '18 at 1:58
@mangusta for example, if the key is 5 and we have 8, 3, 1, 6, 4, 7 ,10, 14 and 3 is BST, the successor to 5 (although 5 is not in the BST) would be 6
– Ben Tilden
Nov 12 '18 at 2:41
have you tried in-order DFS traversal? it is going to give you all bst elements in increasing order so that you may find the successor of any key in linear time
– mangusta
Nov 12 '18 at 3:05
1
ah, seems that the traversal is not necessary at all. you simply save the current node everytime before going left, and then there are several possible cases: 1. you reached the key but it doesn't have a right child. then successor is the key you saved on going left last time. 2. you reached the key and it has a right child, then you move right and then continuously move left until you reach leaf node. 3. the key is not in tree. then you end up with some leaf node and its successor is the key you saved on going left last time
– mangusta
Nov 12 '18 at 3:40