Implement BinarySearchTree class in python The 2019 Stack Overflow Developer Survey Results...
Where to refill my bottle in India?
Did Section 31 appear in Star Trek: The Next Generation?
What is the closest word meaning "respect for time / mindful"
Right tool to dig six foot holes?
Falsification in Math vs Science
Pokemon Turn Based battle (Python)
What to do when moving next to a bird sanctuary with a loosely-domesticated cat?
What is the meaning of Triage in Cybersec world?
Is "plugging out" electronic devices an American expression?
How to support a colleague who finds meetings extremely tiring?
What does ひと匙 mean in this manga and has it been used colloquially?
Aging parents with no investments
Is there a symbol for a right arrow with a square in the middle?
Why did Acorn's A3000 have red function keys?
Why do some words that are not inflected have an umlaut?
Why isn't airport relocation done gradually?
Output the Arecibo Message
Button changing it's text & action. Good or terrible?
What could be the right powersource for 15 seconds lifespan disposable giant chainsaw?
Identify boardgame from Big movie
Did Scotland spend $250,000 for the slogan "Welcome to Scotland"?
How to answer pointed "are you quitting" questioning when I don't want them to suspect
Apparent duplicates between Haynes service instructions and MOT
Why can Shazam fly?
Implement BinarySearchTree class in python
The 2019 Stack Overflow Developer Survey Results Are InPython class to implement a list with a size limitFixing the endlessly loading devices and printers traySerializing output of a match result web scraperImplement OO interfaces in PythonGiven a binary tree, find the maximum path sumCount of Smaller Numbers After SelfImplement a stack class in PythonImplement a queue class in PythonNaming initialization functions in a lookup table based implementation of integer logarithmsImplement LinkedList class in python
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}
0
$begingroup$
I am currently study the basic data structure and trying to implement everything as I go. can anyone give me some feedback about class BinarySearchTree how to make the code more elegant. any review are appreciated.
class TreeNode:
def __init__(self, value=None, left=None, right=None):
self.val = value
self.left = left
self.right = right
class BinarySearchTree:
"""
Database strucutre for binary search tree
1:search
2:insert
3:delete
4:get_height
5:get_min_value
6:get_max_value
"""
def __init__(self, root=None):
self.root = root
def __iter(self, cur):
if cur is not None:
yield from self.__iter(cur.left)
yield cur
yield from self.__iter(cur.right)
def __repr__(self):
cur = self.root
return ''.join(str(i.val) for i in self.__iter(cur))
def insert(self, key):
"""insert node into binary tree based on node's value"""
cur = self.root
if cur is None:
self.root = TreeNode(key)
return
while cur is not None:
if key < cur.val:
if cur.left is None:
cur.left = TreeNode(key)
return
else:
cur = cur.left
elif key > cur.val:
if cur.right is None:
cur.right = TreeNode(key)
return
else:
cur = cur.right
def search(self, key):
"""find node from binary tree based on node's value"""
cur = self.root
if cur is None:
raise KeyError(f'{key} is not found')
while cur is not None:
if key < cur.val:
cur = cur.left
elif key > cur.val:
cur = cur.right
else:
return cur
raise KeyError(f'{key} is not found')
def get_min_value(self):
"""return the min value from tree"""
cur = self.root
while cur is not None and cur.left is not None:
cur = cur.left
return cur.val
def get_max_value(self):
"""return the max value from tree"""
cur = self.root
while cur is not None and cur.right is not None:
cur = cur.right
return cur.val
def get_height(self):
"""return tree height of binary search tree"""
h = 0
return self.__get_height(self.root, h) if self.root else h
def __get_height(self, cur, h):
"""recursion the tree with left subtree and right subtree"""
if cur is None: return h
left_height = self.__get_height(cur.left, h + 1)
right_height = self.__get_height(cur.right, h + 1)
return max(left_height, right_height)
def delete(self, key):
"""delete the node from binary tree based on node's key value"""
if self.root is None: raise KeyError('key is not found')
self.__delete(self.root, key)
def __delete(self, cur, key):
"""recursion the tree to find the node and delete from tree"""
if cur is None: return
if key < cur.val:
cur.left = self.__delete(cur.left, key)
elif key > cur.val:
cur.right = self.__delete(cur.right, key)
else:
if cur.left is None:
return cur.right
elif cur.right is None:
return cur.left
else:
def __get_successor(n):
while n is not None and n.left is not None:
n = n.left
return n
successor = __get_successor(cur)
cur.key = successor.key
cur.right = self.__delete(cur.right, successor.key)
return cur
if __name__ == '__main__':
bst = BinarySearchTree()
bst.insert(6)
bst.insert(2)
bst.insert(8)
bst.insert(0)
bst.insert(4)
bst.insert(7)
bst.insert(9)
bst.insert(3)
bst.insert(5)
print(bst.search(5).val == 5)
print(bst.search(0).val == 0)
print(bst.search(9).val == 9)
print(bst.search(6).val == 6)
try:
bst.search(13)
except KeyError as e:
print(e)
print(bst.get_height() == 4)
bst.delete(5)
print(bst.get_height() == 4)
print(bst.get_max_value() == 9)
print(bst.get_min_value() == 0)
bst.delete(3)
bst.delete(7)
bst.delete(9)
print(bst.get_height() == 3)
print(bst)
python python-3.x
asked 13 mins ago
A.LeeA.Lee
966
$endgroup$
add a comment |
0
$begingroup$
I am currently study the basic data structure and trying to implement everything as I go. can anyone give me some feedback about class BinarySearchTree how to make the code more elegant. any review are appreciated.
class TreeNode:
def __init__(self, value=None, left=None, right=None):
self.val = value
self.left = left
self.right = right
class BinarySearchTree:
"""
Database strucutre for binary search tree
1:search
2:insert
3:delete
4:get_height
5:get_min_value
6:get_max_value
"""
def __init__(self, root=None):
self.root = root
def __iter(self, cur):
if cur is not None:
yield from self.__iter(cur.left)
yield cur
yield from self.__iter(cur.right)
def __repr__(self):
cur = self.root
return ''.join(str(i.val) for i in self.__iter(cur))
def insert(self, key):
"""insert node into binary tree based on node's value"""
cur = self.root
if cur is None:
self.root = TreeNode(key)
return
while cur is not None:
if key < cur.val:
if cur.left is None:
cur.left = TreeNode(key)
return
else:
cur = cur.left
elif key > cur.val:
if cur.right is None:
cur.right = TreeNode(key)
return
else:
cur = cur.right
def search(self, key):
"""find node from binary tree based on node's value"""
cur = self.root
if cur is None:
raise KeyError(f'{key} is not found')
while cur is not None:
if key < cur.val:
cur = cur.left
elif key > cur.val:
cur = cur.right
else:
return cur
raise KeyError(f'{key} is not found')
def get_min_value(self):
"""return the min value from tree"""
cur = self.root
while cur is not None and cur.left is not None:
cur = cur.left
return cur.val
def get_max_value(self):
"""return the max value from tree"""
cur = self.root
while cur is not None and cur.right is not None:
cur = cur.right
return cur.val
def get_height(self):
"""return tree height of binary search tree"""
h = 0
return self.__get_height(self.root, h) if self.root else h
def __get_height(self, cur, h):
"""recursion the tree with left subtree and right subtree"""
if cur is None: return h
left_height = self.__get_height(cur.left, h + 1)
right_height = self.__get_height(cur.right, h + 1)
return max(left_height, right_height)
def delete(self, key):
"""delete the node from binary tree based on node's key value"""
if self.root is None: raise KeyError('key is not found')
self.__delete(self.root, key)
def __delete(self, cur, key):
"""recursion the tree to find the node and delete from tree"""
if cur is None: return
if key < cur.val:
cur.left = self.__delete(cur.left, key)
elif key > cur.val:
cur.right = self.__delete(cur.right, key)
else:
if cur.left is None:
return cur.right
elif cur.right is None:
return cur.left
else:
def __get_successor(n):
while n is not None and n.left is not None:
n = n.left
return n
successor = __get_successor(cur)
cur.key = successor.key
cur.right = self.__delete(cur.right, successor.key)
return cur
if __name__ == '__main__':
bst = BinarySearchTree()
bst.insert(6)
bst.insert(2)
bst.insert(8)
bst.insert(0)
bst.insert(4)
bst.insert(7)
bst.insert(9)
bst.insert(3)
bst.insert(5)
print(bst.search(5).val == 5)
print(bst.search(0).val == 0)
print(bst.search(9).val == 9)
print(bst.search(6).val == 6)
try:
bst.search(13)
except KeyError as e:
print(e)
print(bst.get_height() == 4)
bst.delete(5)
print(bst.get_height() == 4)
print(bst.get_max_value() == 9)
print(bst.get_min_value() == 0)
bst.delete(3)
bst.delete(7)
bst.delete(9)
print(bst.get_height() == 3)
print(bst)
python python-3.x
asked 13 mins ago
A.LeeA.Lee
966
$endgroup$
add a comment |
0
0
0
$begingroup$
I am currently study the basic data structure and trying to implement everything as I go. can anyone give me some feedback about class BinarySearchTree how to make the code more elegant. any review are appreciated.
class TreeNode:
def __init__(self, value=None, left=None, right=None):
self.val = value
self.left = left
self.right = right
class BinarySearchTree:
"""
Database strucutre for binary search tree
1:search
2:insert
3:delete
4:get_height
5:get_min_value
6:get_max_value
"""
def __init__(self, root=None):
self.root = root
def __iter(self, cur):
if cur is not None:
yield from self.__iter(cur.left)
yield cur
yield from self.__iter(cur.right)
def __repr__(self):
cur = self.root
return ''.join(str(i.val) for i in self.__iter(cur))
def insert(self, key):
"""insert node into binary tree based on node's value"""
cur = self.root
if cur is None:
self.root = TreeNode(key)
return
while cur is not None:
if key < cur.val:
if cur.left is None:
cur.left = TreeNode(key)
return
else:
cur = cur.left
elif key > cur.val:
if cur.right is None:
cur.right = TreeNode(key)
return
else:
cur = cur.right
def search(self, key):
"""find node from binary tree based on node's value"""
cur = self.root
if cur is None:
raise KeyError(f'{key} is not found')
while cur is not None:
if key < cur.val:
cur = cur.left
elif key > cur.val:
cur = cur.right
else:
return cur
raise KeyError(f'{key} is not found')
def get_min_value(self):
"""return the min value from tree"""
cur = self.root
while cur is not None and cur.left is not None:
cur = cur.left
return cur.val
def get_max_value(self):
"""return the max value from tree"""
cur = self.root
while cur is not None and cur.right is not None:
cur = cur.right
return cur.val
def get_height(self):
"""return tree height of binary search tree"""
h = 0
return self.__get_height(self.root, h) if self.root else h
def __get_height(self, cur, h):
"""recursion the tree with left subtree and right subtree"""
if cur is None: return h
left_height = self.__get_height(cur.left, h + 1)
right_height = self.__get_height(cur.right, h + 1)
return max(left_height, right_height)
def delete(self, key):
"""delete the node from binary tree based on node's key value"""
if self.root is None: raise KeyError('key is not found')
self.__delete(self.root, key)
def __delete(self, cur, key):
"""recursion the tree to find the node and delete from tree"""
if cur is None: return
if key < cur.val:
cur.left = self.__delete(cur.left, key)
elif key > cur.val:
cur.right = self.__delete(cur.right, key)
else:
if cur.left is None:
return cur.right
elif cur.right is None:
return cur.left
else:
def __get_successor(n):
while n is not None and n.left is not None:
n = n.left
return n
successor = __get_successor(cur)
cur.key = successor.key
cur.right = self.__delete(cur.right, successor.key)
return cur
if __name__ == '__main__':
bst = BinarySearchTree()
bst.insert(6)
bst.insert(2)
bst.insert(8)
bst.insert(0)
bst.insert(4)
bst.insert(7)
bst.insert(9)
bst.insert(3)
bst.insert(5)
print(bst.search(5).val == 5)
print(bst.search(0).val == 0)
print(bst.search(9).val == 9)
print(bst.search(6).val == 6)
try:
bst.search(13)
except KeyError as e:
print(e)
print(bst.get_height() == 4)
bst.delete(5)
print(bst.get_height() == 4)
print(bst.get_max_value() == 9)
print(bst.get_min_value() == 0)
bst.delete(3)
bst.delete(7)
bst.delete(9)
print(bst.get_height() == 3)
print(bst)
python python-3.x
asked 13 mins ago
A.LeeA.Lee
966
$endgroup$
I am currently study the basic data structure and trying to implement everything as I go. can anyone give me some feedback about class BinarySearchTree how to make the code more elegant. any review are appreciated.
class TreeNode:
def __init__(self, value=None, left=None, right=None):
self.val = value
self.left = left
self.right = right
class BinarySearchTree:
"""
Database strucutre for binary search tree
1:search
2:insert
3:delete
4:get_height
5:get_min_value
6:get_max_value
"""
def __init__(self, root=None):
self.root = root
def __iter(self, cur):
if cur is not None:
yield from self.__iter(cur.left)
yield cur
yield from self.__iter(cur.right)
def __repr__(self):
cur = self.root
return ''.join(str(i.val) for i in self.__iter(cur))
def insert(self, key):
"""insert node into binary tree based on node's value"""
cur = self.root
if cur is None:
self.root = TreeNode(key)
return
while cur is not None:
if key < cur.val:
if cur.left is None:
cur.left = TreeNode(key)
return
else:
cur = cur.left
elif key > cur.val:
if cur.right is None:
cur.right = TreeNode(key)
return
else:
cur = cur.right
def search(self, key):
"""find node from binary tree based on node's value"""
cur = self.root
if cur is None:
raise KeyError(f'{key} is not found')
while cur is not None:
if key < cur.val:
cur = cur.left
elif key > cur.val:
cur = cur.right
else:
return cur
raise KeyError(f'{key} is not found')
def get_min_value(self):
"""return the min value from tree"""
cur = self.root
while cur is not None and cur.left is not None:
cur = cur.left
return cur.val
def get_max_value(self):
"""return the max value from tree"""
cur = self.root
while cur is not None and cur.right is not None:
cur = cur.right
return cur.val
def get_height(self):
"""return tree height of binary search tree"""
h = 0
return self.__get_height(self.root, h) if self.root else h
def __get_height(self, cur, h):
"""recursion the tree with left subtree and right subtree"""
if cur is None: return h
left_height = self.__get_height(cur.left, h + 1)
right_height = self.__get_height(cur.right, h + 1)
return max(left_height, right_height)
def delete(self, key):
"""delete the node from binary tree based on node's key value"""
if self.root is None: raise KeyError('key is not found')
self.__delete(self.root, key)
def __delete(self, cur, key):
"""recursion the tree to find the node and delete from tree"""
if cur is None: return
if key < cur.val:
cur.left = self.__delete(cur.left, key)
elif key > cur.val:
cur.right = self.__delete(cur.right, key)
else:
if cur.left is None:
return cur.right
elif cur.right is None:
return cur.left
else:
def __get_successor(n):
while n is not None and n.left is not None:
n = n.left
return n
successor = __get_successor(cur)
cur.key = successor.key
cur.right = self.__delete(cur.right, successor.key)
return cur
if __name__ == '__main__':
bst = BinarySearchTree()
bst.insert(6)
bst.insert(2)
bst.insert(8)
bst.insert(0)
bst.insert(4)
bst.insert(7)
bst.insert(9)
bst.insert(3)
bst.insert(5)
print(bst.search(5).val == 5)
print(bst.search(0).val == 0)
print(bst.search(9).val == 9)
print(bst.search(6).val == 6)
try:
bst.search(13)
except KeyError as e:
print(e)
print(bst.get_height() == 4)
bst.delete(5)
print(bst.get_height() == 4)
print(bst.get_max_value() == 9)
print(bst.get_min_value() == 0)
bst.delete(3)
bst.delete(7)
bst.delete(9)
print(bst.get_height() == 3)
print(bst)
python python-3.x
python python-3.x
asked 13 mins ago
A.LeeA.Lee
966
asked 13 mins ago
A.LeeA.Lee
966
asked 13 mins ago
A.LeeA.Lee
966
asked 13 mins ago
A.LeeA.Lee
966
asked 13 mins ago
A.LeeA.Lee
966
966
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
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: "196"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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%2fcodereview.stackexchange.com%2fquestions%2f217239%2fimplement-binarysearchtree-class-in-python%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
Thanks for contributing an answer to Code Review Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
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%2fcodereview.stackexchange.com%2fquestions%2f217239%2fimplement-binarysearchtree-class-in-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
