Recursive Binary Search Tree Python
I want to implement a binary search tree with element, left & right child and parent in python.
class BSTNode:
""" An internal node for a BST . """
def __init__(self, item):
""" Initialise a BSTNode on creation, with value==item. """
self._element = item
self._leftchild = None
self._rightchild = None
self._parent = None
def __str__(self):
node = self
if node != None:
s = str(node._element)
if node._leftchild:
node._leftchild.__str__()
s = str(node._element)
s+= ' '
elif node._rightchild:
node._rightchild.__str__()
s += str(node._element)
else:
return s
else:
return ''
def add(self, item):
node = self
if node:
if item <node._element :
if node._leftchild is None:
node._leftchild = BSTNode(item)
node._leftchild._parent = node
else:
node._leftchild.add(item)
elif item > node._element:
if node._rightchild is None:
node._rightchild = BSTNode(item)
node._rightchild._parent = node
else:
node._rightchild.add(item)
tree = BSTNode(3);
tree.add(7);
print(tree.__str__());
I wrote this program, but when i run it, it outputs None, but it should output 3 7(the order is inorder traversal). Does anyone knows what i am doing wrong?
python recursion search binary
asked Nov 14 '18 at 17:17
AsYouWereAPxAsYouWereAPx
163
add a comment |
I want to implement a binary search tree with element, left & right child and parent in python.
class BSTNode:
""" An internal node for a BST . """
def __init__(self, item):
""" Initialise a BSTNode on creation, with value==item. """
self._element = item
self._leftchild = None
self._rightchild = None
self._parent = None
def __str__(self):
node = self
if node != None:
s = str(node._element)
if node._leftchild:
node._leftchild.__str__()
s = str(node._element)
s+= ' '
elif node._rightchild:
node._rightchild.__str__()
s += str(node._element)
else:
return s
else:
return ''
def add(self, item):
node = self
if node:
if item <node._element :
if node._leftchild is None:
node._leftchild = BSTNode(item)
node._leftchild._parent = node
else:
node._leftchild.add(item)
elif item > node._element:
if node._rightchild is None:
node._rightchild = BSTNode(item)
node._rightchild._parent = node
else:
node._rightchild.add(item)
tree = BSTNode(3);
tree.add(7);
print(tree.__str__());
I wrote this program, but when i run it, it outputs None, but it should output 3 7(the order is inorder traversal). Does anyone knows what i am doing wrong?
python recursion search binary
asked Nov 14 '18 at 17:17
AsYouWereAPxAsYouWereAPx
163
add a comment |
I want to implement a binary search tree with element, left & right child and parent in python.
class BSTNode:
""" An internal node for a BST . """
def __init__(self, item):
""" Initialise a BSTNode on creation, with value==item. """
self._element = item
self._leftchild = None
self._rightchild = None
self._parent = None
def __str__(self):
node = self
if node != None:
s = str(node._element)
if node._leftchild:
node._leftchild.__str__()
s = str(node._element)
s+= ' '
elif node._rightchild:
node._rightchild.__str__()
s += str(node._element)
else:
return s
else:
return ''
def add(self, item):
node = self
if node:
if item <node._element :
if node._leftchild is None:
node._leftchild = BSTNode(item)
node._leftchild._parent = node
else:
node._leftchild.add(item)
elif item > node._element:
if node._rightchild is None:
node._rightchild = BSTNode(item)
node._rightchild._parent = node
else:
node._rightchild.add(item)
tree = BSTNode(3);
tree.add(7);
print(tree.__str__());
I wrote this program, but when i run it, it outputs None, but it should output 3 7(the order is inorder traversal). Does anyone knows what i am doing wrong?
python recursion search binary
asked Nov 14 '18 at 17:17
AsYouWereAPxAsYouWereAPx
163
I want to implement a binary search tree with element, left & right child and parent in python.
class BSTNode:
""" An internal node for a BST . """
def __init__(self, item):
""" Initialise a BSTNode on creation, with value==item. """
self._element = item
self._leftchild = None
self._rightchild = None
self._parent = None
def __str__(self):
node = self
if node != None:
s = str(node._element)
if node._leftchild:
node._leftchild.__str__()
s = str(node._element)
s+= ' '
elif node._rightchild:
node._rightchild.__str__()
s += str(node._element)
else:
return s
else:
return ''
def add(self, item):
node = self
if node:
if item <node._element :
if node._leftchild is None:
node._leftchild = BSTNode(item)
node._leftchild._parent = node
else:
node._leftchild.add(item)
elif item > node._element:
if node._rightchild is None:
node._rightchild = BSTNode(item)
node._rightchild._parent = node
else:
node._rightchild.add(item)
tree = BSTNode(3);
tree.add(7);
print(tree.__str__());
I wrote this program, but when i run it, it outputs None, but it should output 3 7(the order is inorder traversal). Does anyone knows what i am doing wrong?
python recursion search binary
python recursion search binary
asked Nov 14 '18 at 17:17
AsYouWereAPxAsYouWereAPx
163
asked Nov 14 '18 at 17:17
AsYouWereAPxAsYouWereAPx
163
asked Nov 14 '18 at 17:17
AsYouWereAPxAsYouWereAPx
163
asked Nov 14 '18 at 17:17
AsYouWereAPxAsYouWereAPx
163
asked Nov 14 '18 at 17:17
AsYouWereAPxAsYouWereAPx
163
163
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Your __str__ method is incorrect. Specifically, you call __str__() of the left and right children but don't do anything with the result. Also note that a node can have both left and right children (if...elif will only check for one). You're also not not returing s if you hit one of your if or elif blocks.
You can simplify it to:
def __str__(self):
node = self
if node != None:
s = str(node._element)
if node._leftchild:
s = node._leftchild.__str__() + s
if node._rightchild:
s += ' ' + node._rightchild.__str__()
return s
return ''
answered Nov 14 '18 at 17:32
sliderslider
8,37311130
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%2f53305568%2frecursive-binary-search-tree-python%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
Your __str__ method is incorrect. Specifically, you call __str__() of the left and right children but don't do anything with the result. Also note that a node can have both left and right children (if...elif will only check for one). You're also not not returing s if you hit one of your if or elif blocks.
You can simplify it to:
def __str__(self):
node = self
if node != None:
s = str(node._element)
if node._leftchild:
s = node._leftchild.__str__() + s
if node._rightchild:
s += ' ' + node._rightchild.__str__()
return s
return ''
answered Nov 14 '18 at 17:32
sliderslider
8,37311130
add a comment |
Your __str__ method is incorrect. Specifically, you call __str__() of the left and right children but don't do anything with the result. Also note that a node can have both left and right children (if...elif will only check for one). You're also not not returing s if you hit one of your if or elif blocks.
You can simplify it to:
def __str__(self):
node = self
if node != None:
s = str(node._element)
if node._leftchild:
s = node._leftchild.__str__() + s
if node._rightchild:
s += ' ' + node._rightchild.__str__()
return s
return ''
answered Nov 14 '18 at 17:32
sliderslider
8,37311130
add a comment |
Your __str__ method is incorrect. Specifically, you call __str__() of the left and right children but don't do anything with the result. Also note that a node can have both left and right children (if...elif will only check for one). You're also not not returing s if you hit one of your if or elif blocks.
You can simplify it to:
def __str__(self):
node = self
if node != None:
s = str(node._element)
if node._leftchild:
s = node._leftchild.__str__() + s
if node._rightchild:
s += ' ' + node._rightchild.__str__()
return s
return ''
answered Nov 14 '18 at 17:32
sliderslider
8,37311130
Your __str__ method is incorrect. Specifically, you call __str__() of the left and right children but don't do anything with the result. Also note that a node can have both left and right children (if...elif will only check for one). You're also not not returing s if you hit one of your if or elif blocks.
You can simplify it to:
def __str__(self):
node = self
if node != None:
s = str(node._element)
if node._leftchild:
s = node._leftchild.__str__() + s
if node._rightchild:
s += ' ' + node._rightchild.__str__()
return s
return ''
answered Nov 14 '18 at 17:32
sliderslider
8,37311130
edited Nov 14 '18 at 17:39
answered Nov 14 '18 at 17:32
sliderslider
8,37311130
answered Nov 14 '18 at 17:32
sliderslider
8,37311130
answered Nov 14 '18 at 17:32
sliderslider
8,37311130
8,37311130
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%2f53305568%2frecursive-binary-search-tree-python%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
