# # linked representation -- recursive
class Node:
def __init__(self, data = None):
self.data = data
self.left = None
self.right = None
class BT:
def __init__(self):
self.root = None
def addNode(self, newData):
if self.root == None:
self.root = Node(newData)
else:
self.addNodeHelper(self.root, newData)
def addNodeHelper(self,node,newData):
if newData > node.data:
if node.right == None:
node.right = Node(newData)
else:
self.addNodeHelper(node.right, newData)
elif newData < node.data:
if node.left == None:
node.left = Node(newData)
else:
self.addNodeHelper(node.left, newData)
def findNode(self, searchitem):
return self.findNodeHelper(self.root, searchitem)
def findNodeHelper(self, node, searchitem):
if node is None:
return False
elif node.data == searchitem:
return True
elif searchitem > node.data:
return self.findNodeHelper(node.right, searchitem)
elif searchitem < node.data:
return self.findNodeHelper(node.left, searchitem)
def inOrderTraversal(self):
result = []
self.iothelper(self.root, result)
return result
def iothelper(self, node, result):
if node.left != None:
self.iothelper(node.left, result)
result.append(node.data)
if node.right != None:
self.iothelper(node.right, result)
tree = BT()
tree.addNode(5)
tree.addNode(3)
tree.addNode(7)
tree.addNode(4)
tree.addNode(6)
print(tree.inOrderTraversal()) # Output: 3 4 5 6 7[3, 4, 5, 6, 7]
'''
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
Step-by-Step Traversal
Step 1: Start at 8
Call iothelper(8), go left → iothelper(3)
Step 2: Move to leftmost node (1)
Call iothelper(3), go left → iothelper(1)
1.left is None, so return.
Visit 1 (append 1 to list).
1.right is None, so return.
Back to 3 (Parent Node).
Visit 3 (append 3 to list). ✅ (This happens before visiting 6)
Go right → iothelper(6).
Step 3: Process 6
Call iothelper(6), go left → iothelper(4)
4.left is None, so return.
Visit 4 (append 4 to list).
4.right is None, so return.
Back to 6 (Parent Node).
Visit 6 (append 6 to list).
Go right → iothelper(7).
Step 4: Process 7
7.left is None, so return.
Visit 7 (append 7 to list).
7.right is None, so return.
Back to 8 (Parent Node).
Step 5: Process 8
Visit 8 (append 8 to list).
Go right → iothelper(10).
Step 6: Process 10
10.left is None, so return.
Visit 10 (append 10 to list).
Go right → iothelper(14).
Step 7: Process 14
Go left → iothelper(13)
13.left is None, so return.
Visit 13 (append 13 to list).
13.right is None, so return.
Back to 14 (Parent Node).
Visit 14 (append 14 to list).
14.right is None, so return.
Traversal is now complete! 🎯
'''# # linked representation -- iterative
class Node:
def __init__(self, data = None):
self.data = data
self.left = None
self.right = None
class BT:
def __init__(self):
self.root = None
def addNode(self, newdata):
if self.root == None:
self.root = Node(newdata)
else:
cur = self.root
while cur != None: #or while True
if newdata > cur.data:
if cur.right == None:
cur.right = Node(newdata)
break
else:
cur = cur.right
if newdata < cur.data:
if cur.left == None:
cur.left = Node(newdata)
break
else:
cur = cur.left
def findNode(self, search):
cur = self.root
while cur != None and cur.data != search:
if search > cur.data:
cur = cur.right
else:
cur = cur.left
if cur == None:
return False
elif cur.data == search:
return True
def inOrderTraversal(self):
result = []
self.iothelper(self.root, result)
return result
def iothelper(self, node, result):
if node.left != None:
self.iothelper(node.left, result)
result.append(node.data)
if node.right != None:
self.iothelper(node.right, result)
tree = BT()
tree.addNode(5)
tree.addNode(3)
tree.addNode(7)
tree.addNode(4)
tree.addNode(6)
print(tree.inOrderTraversal()) # Output: 3 4 5 6 7[3, 4, 5, 6, 7]
# # array of nodes -- without free spaced ll
# 1 based
class Node:
def __init__(self, data = None):
self.data = data
self.left = 0
self.right = 0
class BT:
def __init__(self, size = 7):
self.nullptr = 0
self.root = self.nullptr
self.freeptr = 1
self.size = size
self.tree = [Node() for i in range(self.size + 1)] ##Yes, technically there are 8 nodes allocated, but the node at index 0 is never used.
#self.tree[0] acts as nullptr (0).
#Usable nodes: Only 1 to size (i.e., 1 to 7 in this case).
def addNode(self, newdata):
##need to check if self.tree is full first!
if self.freeptr > self.size: ##dh equal because my freeptr starts from 1 and not 0!!! so not >= like in 0 based but >
print("Tree full! Cant add")
return
newNodePtr = self.freeptr
self.tree[newNodePtr].data = newdata
self.tree[newNodePtr].left = self.nullptr
self.tree[newNodePtr].right = self.nullptr
self.freeptr += 1
##forgot to check root
if self.root == self.nullptr:
self.root = newNodePtr
return #need to return!
cur = self.root
while True:
if newdata < self.tree[cur].data: ##did not put self.tree in front. cur is an index so we need refer to the array by self.table[cur].data
if self.tree[cur].left == self.nullptr: ##cur is an index! to refer to the node, we need to use self.tree[cur]. --> self.tree[cur].left to refer to left pointer of node with index cur
self.tree[cur].left = newNodePtr
break
else:
cur = self.tree[cur].left
elif newdata > self.tree[cur].data:
if self.tree[cur].right == self.nullptr:
self.tree[cur].right = newNodePtr
break
else:
cur = self.tree[cur].right
def findNode(self, searchitem):
cur = self.root
while cur != self.nullptr and self.tree[cur].data != searchitem:
if searchitem > self.tree[cur].data:
cur = self.tree[cur].right
else:
cur = self.tree[cur].left
return cur
# Initialize tree
tree = BT(size=7)
# Insert values
values = [8, 3, 10, 1, 6, 14, 4]
for val in values:
tree.addNode(val)
# Test findNode function
print(tree.findNode(6)) # ✅ Expected: True (exists)
print(tree.findNode(10)) # ✅ Expected: True (exists)
print(tree.findNode(2)) # ✅ Expected: False (does not exist)
print(tree.findNode(14)) # ✅ Expected: True (exists)
print(tree.findNode(20)) # ✅ Expected: False (does not exist)
# Test inserting into a full tree
tree.addNode(7) # ❌ Should print "Tree full! Can't add more nodes."
tree.addNode(15) # ❌ Should print "Tree full! Can't add more nodes."5 3 0 6 0 Tree full! Cant add Tree full! Cant add
# # array of nodes -- with free spaced ll
# 1 based
class Node:
def __init__(self):
self.data = None
self.left = 0
self.right = 0
class BT:
def __init__(self, size = 7):
self.nullptr = 0
self.root = self.nullptr
self.size = size
self.tree = [Node() for i in range(size + 1)]
self.freeptr = 1
for i in range(1, size): #1, 2, 3, 4, 5, 6
self.tree[i].left = i + 1
self.tree[i].right = self.nullptr
self.tree[size].left = self.nullptr
def addNode(self, newdata):
if self.freeptr == self.nullptr: ##checks if still have free spaced!! must do this!
print("Tree full, cannot insert")
return
newNodePtr = self.freeptr
self.freeptr = self.tree[self.freeptr].left ##shld do this first
self.tree[newNodePtr].data = newdata
self.tree[newNodePtr].left = self.nullptr
self.tree[newNodePtr].right = self.nullptr
if self.root == self.nullptr:
self.root = newNodePtr
return
cur = self.root
while True:
if newdata > self.tree[cur].data:
if self.tree[cur].right == self.nullptr:
self.tree[cur].right = newNodePtr
break
cur = self.tree[cur].right
elif newdata < self.tree[cur].data:
if self.tree[cur].left == self.nullptr:
self.tree[cur].left = newNodePtr
break
cur = self.tree[cur].left
def findNode(self, searchitem):
cur = self.root
while cur != self.nullptr and self.tree[cur].data != searchitem:
if searchitem > self.tree[cur].data:
cur = self.tree[cur].right
elif searchitem < self.tree[cur].data:
cur = self.tree[cur].left
return cur
# Initialize tree
tree = BT(size=7)
# Insert values
values = [8, 3, 10, 1, 6, 14, 4]
for val in values:
tree.addNode(val)
# Test findNode function
print(tree.findNode(6)) # ✅ Expected: True (exists)
print(tree.findNode(10)) # ✅ Expected: True (exists)
print(tree.findNode(2)) # ✅ Expected: False (does not exist)
print(tree.findNode(14)) # ✅ Expected: True (exists)
print(tree.findNode(20)) # ✅ Expected: False (does not exist)
# Test inserting into a full tree
tree.addNode(7) # ❌ Should print "Tree full! Cannot add more nodes."
tree.addNode(15) # ❌ Should print "Tree full! Cannot add more nodes."5 3 0 6 0 Tree full, cannot insert Tree full, cannot insert