Binary Search Tree implementation with topological validation
0
$begingroup$
import sys
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
def __str__(self):
return f"{self.value} "
class Sum:
def __init__(self, val):
self.s = val
def getS(self):
return self.s
def update(self, val):
self.s += val
class BST:
def __init__(self):
self.root = None
def insert(self, key):
curr = self.root
parent = None
if self.root:
while curr and curr.value != key:
parent = curr
if curr.value < key:
curr = curr.right
else:
curr = curr.left
else:
self.root = Node(key)
return
if parent:
if parent.value < key:
parent.right = Node(key)
else:
parent.left = Node(key)
def delete(self, key):
pass
def _doFind(self, root, key):
if root:
if root.value == key:
return root
if root.value < key:
self._doFind(root.right, key)
else:
self._doFind(root.left, key)
def find(self, key):
self._doFind(self.root, key)
def _inorder(self, root):
if root:
self._inorder(root.left)
print(root, " ")
self._inorder(root.right)
def inorder(self):
self._inorder(self.root)
def _preorder(self, root):
if root:
print(root, " ")
self._preorder(root.left)
self._preorder(root.right)
def preorder(self):
self._preorder(self.root)
def _postorder(self, root):
if root:
self._postorder(root.left)
self._postorder(root.right)
print(root, " ")
def postorder(self):
self._postorder(self.root)
def sumRToL(self, root, s):
if root:
self.sumRToL(root.right, s)
s.update(root.value)
root.value = s.getS()
self.sumRToL(root.left, s)
def sumelementsfromRtoLinplace(self):
s = Sum(0)
self.sumRToL(self.root, s)
def validate(self, root, low, high):
# Look for iterative solutions as well, probably using some stack
return (not root) or (low <= root.value <= high and (
self.validate(root.left, low, root.value) and self.validate(root.right, root.value, high)))
def validatebst(self):
max = sys.maxsize
min = -sys.maxsize - 1
return self.validate(self.root, min, max)
def isSameTree(self, p, q):
# Task : Can a level order solve this. Any non-recursive solutions as stack depth is not reliable?
"""
Checks the value as well as topological order
:type p: Node
:type q: Node
:rtype: bool
"""
if not p and not q:
return True
elif p and q and p.value == q.value:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return False
def test_main():
bst = BST()
bst.insert(1)
bst.insert(2)
bst.insert(3)
bst.insert(4)
bst.insert(5)
# bst.root.left = Node(34) # Mess up the tree
# bst.insert(2)
# bst.insert(3)
# bst.insert(4)
# bst.insert(5)
# bst.sumelementsfromRtoLinplace()
# bst.inorder()
bst1 = BST()
bst1.insert(1)
bst1.insert(2)
bst1.insert(3)
bst1.insert(4)
bst1.insert(5)
print('Same tree : ', bst.isSameTree(bst.root, bst1.root))
print("Valid Tree : ", bst.validatebst())
if __name__ == '__main__':
test_main()
P.S : I had to create the Sum class as there's no way to share the same primitive int across stack calls as there is no pass by reference in Python. I wanted to avoid using global variables throughout.
python tree reinventing-the-wheel
asked 1 hour ago
piepipiepi
438316
$endgroup$
add a comment |
0
$begingroup$
import sys
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
def __str__(self):
return f"{self.value} "
class Sum:
def __init__(self, val):
self.s = val
def getS(self):
return self.s
def update(self, val):
self.s += val
class BST:
def __init__(self):
self.root = None
def insert(self, key):
curr = self.root
parent = None
if self.root:
while curr and curr.value != key:
parent = curr
if curr.value < key:
curr = curr.right
else:
curr = curr.left
else:
self.root = Node(key)
return
if parent:
if parent.value < key:
parent.right = Node(key)
else:
parent.left = Node(key)
def delete(self, key):
pass
def _doFind(self, root, key):
if root:
if root.value == key:
return root
if root.value < key:
self._doFind(root.right, key)
else:
self._doFind(root.left, key)
def find(self, key):
self._doFind(self.root, key)
def _inorder(self, root):
if root:
self._inorder(root.left)
print(root, " ")
self._inorder(root.right)
def inorder(self):
self._inorder(self.root)
def _preorder(self, root):
if root:
print(root, " ")
self._preorder(root.left)
self._preorder(root.right)
def preorder(self):
self._preorder(self.root)
def _postorder(self, root):
if root:
self._postorder(root.left)
self._postorder(root.right)
print(root, " ")
def postorder(self):
self._postorder(self.root)
def sumRToL(self, root, s):
if root:
self.sumRToL(root.right, s)
s.update(root.value)
root.value = s.getS()
self.sumRToL(root.left, s)
def sumelementsfromRtoLinplace(self):
s = Sum(0)
self.sumRToL(self.root, s)
def validate(self, root, low, high):
# Look for iterative solutions as well, probably using some stack
return (not root) or (low <= root.value <= high and (
self.validate(root.left, low, root.value) and self.validate(root.right, root.value, high)))
def validatebst(self):
max = sys.maxsize
min = -sys.maxsize - 1
return self.validate(self.root, min, max)
def isSameTree(self, p, q):
# Task : Can a level order solve this. Any non-recursive solutions as stack depth is not reliable?
"""
Checks the value as well as topological order
:type p: Node
:type q: Node
:rtype: bool
"""
if not p and not q:
return True
elif p and q and p.value == q.value:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return False
def test_main():
bst = BST()
bst.insert(1)
bst.insert(2)
bst.insert(3)
bst.insert(4)
bst.insert(5)
# bst.root.left = Node(34) # Mess up the tree
# bst.insert(2)
# bst.insert(3)
# bst.insert(4)
# bst.insert(5)
# bst.sumelementsfromRtoLinplace()
# bst.inorder()
bst1 = BST()
bst1.insert(1)
bst1.insert(2)
bst1.insert(3)
bst1.insert(4)
bst1.insert(5)
print('Same tree : ', bst.isSameTree(bst.root, bst1.root))
print("Valid Tree : ", bst.validatebst())
if __name__ == '__main__':
test_main()
P.S : I had to create the Sum class as there's no way to share the same primitive int across stack calls as there is no pass by reference in Python. I wanted to avoid using global variables throughout.
python tree reinventing-the-wheel
asked 1 hour ago
piepipiepi
438316
$endgroup$
add a comment |
0
0
0
$begingroup$
import sys
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
def __str__(self):
return f"{self.value} "
class Sum:
def __init__(self, val):
self.s = val
def getS(self):
return self.s
def update(self, val):
self.s += val
class BST:
def __init__(self):
self.root = None
def insert(self, key):
curr = self.root
parent = None
if self.root:
while curr and curr.value != key:
parent = curr
if curr.value < key:
curr = curr.right
else:
curr = curr.left
else:
self.root = Node(key)
return
if parent:
if parent.value < key:
parent.right = Node(key)
else:
parent.left = Node(key)
def delete(self, key):
pass
def _doFind(self, root, key):
if root:
if root.value == key:
return root
if root.value < key:
self._doFind(root.right, key)
else:
self._doFind(root.left, key)
def find(self, key):
self._doFind(self.root, key)
def _inorder(self, root):
if root:
self._inorder(root.left)
print(root, " ")
self._inorder(root.right)
def inorder(self):
self._inorder(self.root)
def _preorder(self, root):
if root:
print(root, " ")
self._preorder(root.left)
self._preorder(root.right)
def preorder(self):
self._preorder(self.root)
def _postorder(self, root):
if root:
self._postorder(root.left)
self._postorder(root.right)
print(root, " ")
def postorder(self):
self._postorder(self.root)
def sumRToL(self, root, s):
if root:
self.sumRToL(root.right, s)
s.update(root.value)
root.value = s.getS()
self.sumRToL(root.left, s)
def sumelementsfromRtoLinplace(self):
s = Sum(0)
self.sumRToL(self.root, s)
def validate(self, root, low, high):
# Look for iterative solutions as well, probably using some stack
return (not root) or (low <= root.value <= high and (
self.validate(root.left, low, root.value) and self.validate(root.right, root.value, high)))
def validatebst(self):
max = sys.maxsize
min = -sys.maxsize - 1
return self.validate(self.root, min, max)
def isSameTree(self, p, q):
# Task : Can a level order solve this. Any non-recursive solutions as stack depth is not reliable?
"""
Checks the value as well as topological order
:type p: Node
:type q: Node
:rtype: bool
"""
if not p and not q:
return True
elif p and q and p.value == q.value:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return False
def test_main():
bst = BST()
bst.insert(1)
bst.insert(2)
bst.insert(3)
bst.insert(4)
bst.insert(5)
# bst.root.left = Node(34) # Mess up the tree
# bst.insert(2)
# bst.insert(3)
# bst.insert(4)
# bst.insert(5)
# bst.sumelementsfromRtoLinplace()
# bst.inorder()
bst1 = BST()
bst1.insert(1)
bst1.insert(2)
bst1.insert(3)
bst1.insert(4)
bst1.insert(5)
print('Same tree : ', bst.isSameTree(bst.root, bst1.root))
print("Valid Tree : ", bst.validatebst())
if __name__ == '__main__':
test_main()
P.S : I had to create the Sum class as there's no way to share the same primitive int across stack calls as there is no pass by reference in Python. I wanted to avoid using global variables throughout.
python tree reinventing-the-wheel
asked 1 hour ago
piepipiepi
438316
$endgroup$
import sys
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
def __str__(self):
return f"{self.value} "
class Sum:
def __init__(self, val):
self.s = val
def getS(self):
return self.s
def update(self, val):
self.s += val
class BST:
def __init__(self):
self.root = None
def insert(self, key):
curr = self.root
parent = None
if self.root:
while curr and curr.value != key:
parent = curr
if curr.value < key:
curr = curr.right
else:
curr = curr.left
else:
self.root = Node(key)
return
if parent:
if parent.value < key:
parent.right = Node(key)
else:
parent.left = Node(key)
def delete(self, key):
pass
def _doFind(self, root, key):
if root:
if root.value == key:
return root
if root.value < key:
self._doFind(root.right, key)
else:
self._doFind(root.left, key)
def find(self, key):
self._doFind(self.root, key)
def _inorder(self, root):
if root:
self._inorder(root.left)
print(root, " ")
self._inorder(root.right)
def inorder(self):
self._inorder(self.root)
def _preorder(self, root):
if root:
print(root, " ")
self._preorder(root.left)
self._preorder(root.right)
def preorder(self):
self._preorder(self.root)
def _postorder(self, root):
if root:
self._postorder(root.left)
self._postorder(root.right)
print(root, " ")
def postorder(self):
self._postorder(self.root)
def sumRToL(self, root, s):
if root:
self.sumRToL(root.right, s)
s.update(root.value)
root.value = s.getS()
self.sumRToL(root.left, s)
def sumelementsfromRtoLinplace(self):
s = Sum(0)
self.sumRToL(self.root, s)
def validate(self, root, low, high):
# Look for iterative solutions as well, probably using some stack
return (not root) or (low <= root.value <= high and (
self.validate(root.left, low, root.value) and self.validate(root.right, root.value, high)))
def validatebst(self):
max = sys.maxsize
min = -sys.maxsize - 1
return self.validate(self.root, min, max)
def isSameTree(self, p, q):
# Task : Can a level order solve this. Any non-recursive solutions as stack depth is not reliable?
"""
Checks the value as well as topological order
:type p: Node
:type q: Node
:rtype: bool
"""
if not p and not q:
return True
elif p and q and p.value == q.value:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return False
def test_main():
bst = BST()
bst.insert(1)
bst.insert(2)
bst.insert(3)
bst.insert(4)
bst.insert(5)
# bst.root.left = Node(34) # Mess up the tree
# bst.insert(2)
# bst.insert(3)
# bst.insert(4)
# bst.insert(5)
# bst.sumelementsfromRtoLinplace()
# bst.inorder()
bst1 = BST()
bst1.insert(1)
bst1.insert(2)
bst1.insert(3)
bst1.insert(4)
bst1.insert(5)
print('Same tree : ', bst.isSameTree(bst.root, bst1.root))
print("Valid Tree : ", bst.validatebst())
if __name__ == '__main__':
test_main()
P.S : I had to create the Sum class as there's no way to share the same primitive int across stack calls as there is no pass by reference in Python. I wanted to avoid using global variables throughout.
python tree reinventing-the-wheel
python tree reinventing-the-wheel
asked 1 hour ago
piepipiepi
438316
asked 1 hour ago
piepipiepi
438316
asked 1 hour ago
piepipiepi
438316
asked 1 hour ago
piepipiepi
438316
asked 1 hour ago
piepipiepi
438316
438316
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%2f214806%2fbinary-search-tree-implementation-with-topological-validation%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%2f214806%2fbinary-search-tree-implementation-with-topological-validation%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
