Skip to content

Instantly share code, notes, and snippets.

@dantof
Forked from davidlares/bst.py
Created March 19, 2021 16:27
Show Gist options
  • Save dantof/acd63065b520486bade9718e371f7db2 to your computer and use it in GitHub Desktop.
Save dantof/acd63065b520486bade9718e371f7db2 to your computer and use it in GitHub Desktop.
Binary search tree with Python
#/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)
#!/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