Notes on Trees
Binary Tree
Terminology
-
Root is the topmost node of the tree
-
Edge is the link between two nodes
-
Child is a node that has a parent node
-
Parent is a node that has an edge to a child node
-
Leaf is a node that does not have a child node in the tree
-
Height is the length of the longest path to a leaf
-
Depth is the length of the path to its root
Binary Search Tree
Binary search tree is also called an ordered binary tree.
Properties:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
Implementation:
Node Class:
Although a tree can be made to be doubly linked, that is both parent and children have connection to each other, here I have chosen a simple one way connected tree.
Other than its value, a single Node has a left child and a right child.
class Node:
def __init__(self,data,left=None,right=None):
self.left = left
self.right = right
self.data = data
Implementation
Insert Method
Inserting into Binary Tree can be done by using recursion.
- Check if number > or < or = to the value at a node (starting at root)
- If < then apply 1 recursively on left sub-tree, till you find an optimal place as a leaf
- If > then apply 1 recursively on right sub-tree, till you find an optimal point in the right sub-tree
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
Lookup Method
In lookup, find the parent and the node corresponding to a number. The logic is similar to insertion. Recursively check the left and the right sub-trees
def lookup(self,data,parent=None):
if data<self.data:
if self.left is None:
return None,None
else:
return self.left.lookup(data,self)
elif data>self.data:
if self.right is None:
return None,None
else:
return self.right.lookup(data,self)
else:
return self,parent
Deletion is a slightly different beast. There are following cases that need handling:
- Delete a leaf node
- Delete a node with only one child
- Delete a node with two children
- Delete the root node
Deleting the root node is a special case of 3.
Look at the comments to find how each of the following were done.
def delete(self,data):
a , b = self.lookup(data)
if (a == None):
print("data not found")
return False
elif (b == None and a!= None): #
if a.left == None and a.right == None: #1. Delete a leaf node
a.data = None
if a.left == None and a.right != None: #2. Delete a node with only one child
a = a.right
if a.left != None and a.right == None:
a = a.left
if a.left != None and a.right!=None:
c = a.right
t = c
while(c.left!=None and c.right!=None):
t = c
c = c.left
t.left = None
a.data = c.data
return True
else:
if a.data < b.data: # 3. Delete a node with two children
loc = 0
elif a.data > b.data:
loc = 1
if a.left == None and a.right == None:
if loc == 0:
b.left = None
elif loc == 1:
b.right = None
if a.left == None and a.right != None:
if loc == 0:
b.left = a.right
elif loc == 1:
b.right = a.right
if a.left != None and a.right == None:
if loc == 0:
b.left = a.left
elif loc == 1:
b.right = a.left
if a.left != None and a.right!=None: # 4. Delete the root node
c = a.right
while(c.left!=None and c.right!=None):
temp = c
c = c.left
temp.left = None
a.data = c.data
return True
Traversals
Inorder Traversal
Inorder traversal, the order is left —> Node —> Right
def inorder(self):
if self.left is not None:
self.left.inorder()
print(self.data, end = ' ')
if self.right is not None:
self.right.inorder()
Preorder Traversal
Inorder traversal, the order is Node —> Left —> Right
def preorder(self):
print(self.data, end = ' ')
if self.left is not None:
self.left.preorder()
if self.right is not None:
self.right.preorder()
Postorder Traversal
Inorder traversal, the order is Right —> Node —> left
def postorder(self):
if self.right is not None:
self.right.postorder()
print(self.data, end = ' ')
if self.left is not None:
self.left.postorder()
BFS and DFS
Pre,In and Post Order traversal are all Depth-First.
BFS or level order is a traversal where we traverse all elements at a particular level first.
BFS we’ll implement here
Core idea is to use a FIFO technique to print all elements on a level everytime.
def levelorder(self):
q = list()
if self.data is None:
return False
if self.data is not None:
q.append(self)
while(len(q)!=0):
temp = q.pop()
print(temp.data, end= " ")
if temp.left!=None:
q.append(temp.left)
if temp.right!=None:
q.append(temp.right)
Driver Code
root = Node(10)
root.insert(6)
root.insert(11)
root.insert(7)
root.insert(5)
print("Inorder")
root.inorder() #DFS
print("Preorder")
root.preorder() #DFS
print("Postorder")
root.postorder() #DFS
print("Levelorder")
root.levelorder() #BFS
Output
Inorder
5 6 7 10 11
Preorder
10 6 5 7 11
Postorder
11 10 7 6 5
levelorder
10 11 6 7 5
Credits:
