-
-
Save dantof/acd63065b520486bade9718e371f7db2 to your computer and use it in GitHub Desktop.
Binary search tree with Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#/usr/bin/python3 | |
# binary search tree | |
class Node: | |
val = 0 | |
left = 0 | |
right = 0 | |
def __init__(self, val): | |
self.val = val | |
class BST: | |
def __init__(self, val): | |
self.root = Node(val) | |
def insert(self, val, node): | |
if node.val < val: | |
# go right | |
if node.right: | |
self.insert(val, node.right) | |
else: | |
node.right = Node(val) | |
elif val < node.val: | |
if node.left: | |
# go left | |
self.insert(val, node.left) | |
else: | |
node.left = Node(val) | |
else: | |
print(val, "Already in tree") | |
def number_of_leaves(self,node): | |
if node.left and node.right: | |
return self.number_of_leaves(node.left) + self.number_of_leaves(node.right) | |
elif node.left: | |
return self.number_of_leaves(node.left) | |
elif node.right: | |
return self.number_of_leaves(node.right) | |
else: | |
#leave - no left of right | |
return 1 | |
def number_of_leaves_i(self): | |
leaves = 0 | |
nodes = [self.root] | |
while nodes: | |
node = nodes[0] | |
if node.left: | |
nodes.append(node.left) | |
if node.right: | |
nodes.append(node.right) | |
if (not node.left) and (not node.right): | |
leaves += 1 | |
del nodes[0] | |
return leaves | |
def height(self, node): | |
if node.left and node.right: | |
return 1 + max(self.height(node.left), self.height(node.right)) | |
elif node.left: | |
return 1 + self.height(node.left) | |
elif node.right: | |
return 1 + self.height(node.right) | |
else: | |
return 1 | |
def is_identical(self, second_root): | |
nodes1 = [self.root] | |
nodes2 = [second_root] | |
while(nodes1 and nodes2): | |
node = nodes1[0] | |
node2 = nodes2[0] | |
if node.val == node2.val: | |
if node.left: | |
nodes1.append(node.left) | |
if node.right: | |
nodes1.append(node.right) | |
if node2.left: | |
nodes2.append(node2.left) | |
if node2.right: | |
nodes2.append(node2.right) | |
else: | |
return False | |
del nodes1[0] | |
del nodes2[0] | |
return len(nodes1) == len(nodes2) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/python | |
import BST | |
tree = BST.BST(10) | |
# insertions | |
tree.insert(5, tree.root) | |
tree.insert(15, tree.root) | |
tree.insert(25, tree.root) | |
tree.insert(22, tree.root) | |
tree.insert(35, tree.root) | |
tree2 = BST.BST(10) | |
# insertions | |
tree2.insert(5, tree2.root) | |
tree2.insert(15, tree2.root) | |
tree2.insert(25, tree2.root) | |
tree2.insert(22, tree2.root) | |
tree2.insert(35, tree2.root) | |
print(tree.number_of_leaves(tree.root)) | |
print(tree.number_of_leaves_i()) | |
print(tree.height(tree.root)) | |
# check identical | |
print(tree.is_identical(tree2.root)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment