[Data Structure] Topic 8: Tree

Authored by Tony Feng

Created on March 27th, 2022

Last Modified on March 28th, 2022

Understanding Trees

Main Concepts

A tree is non-linear and a hierarchical data structure.
It consists of a collection of nodes such that each node of the tree stores a value and a list of references to their children.
Different tree data structures allow quicker and easier access to the data as it is a non-linear data structure.

Tree Terminologies

Term	Explanation
Node	1. A node is an entity that contains a key or value and pointers to its child nodes. 2. Root is the topmost node of a tree. 3. The last nodes of each path are called leaf nodes or external nodes that do not contain a link/pointer to child nodes. 4. The node having at least a child node is called an internal node. 5. The node which is a predecessor of a node is called the parent node of that node. 6. The node which is the immediate successor of a node is called the child node of that node. 7. Any predecessor nodes on the path of the root to that node are called Ancestors of that node. 8. Any successor node on the path from the leaf node to that node are the descendants of the node. 9. Children of the same parent node are called siblings.
Edge	It is the link between any two nodes.
Depth of a Node	The depth of a node is the number of edges from the node to the tree’s root node (from bottom to top).
Height of a Node	1. The number of edges on the longest path from that node to a leaf (from top to bottom). 2. The height of a Tree is the height of the root node or the depth of the deepest node.
Level of a node	1. The level of a node is defined by 1 + the number of connections between the node and the root. 2. The level of the root is 1.
Degree of a Node	It is the total count of subtrees attached to that node.

Binary Trees

Classifications
- Full/ proper/ strict Binary tree
  - It can be defined as the tree in which each node must contain 2 children except the leaf nodes.
- Complete Binary tree
  - It is a tree in which all the nodes are completely filled except the last level.
  - In the last level, all the nodes must be as left as possible.
- Perfect Binary tree
  - A tree is a perfect binary tree if all the internal nodes have 2 children.
  - All the leaf nodes are at the same level.
- Degenerate Binary tree
  - It is a tree in which all the internal nodes have only one children.
- Balanced Binary tree
  - The tree, also referred to as a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1.
Traverse
- Preorder traverse
  - Visit root node
  - Visit all the nodes in the left subtree
  - Visit all the nodes in the right subtree
- Inorder traverse
  - First, visit all the nodes in the left subtree
  - Then the root node
  - Visit all the nodes in the right subtree
- Postorder traverse
  - Visit all the nodes in the left subtree
  - Visit all the nodes in the right subtree
  - Visit the root node

Set Implementation in Python

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179


# Binary search tree
class binarySearchTree:
    def __init__(self,val=None):
        self.val = val
        self.left = None
        self.right = None

    def insert(self,val):
        # check if there is no root
        if (self.val == None):
            self.val = val
        # check where to insert
        else:
            # check for duplicate then stop and return
            if val == self.val: return 'no duplicates allowed in binary search tree'
            # check if value to be inserted < currentNode's value
            if (val < self.val):
                # check if there is a left node to currentNode if true then recurse
                if(self.left):
                    self.left.insert(val)
                # insert where left of currentNode when currentNode.left=None
                else: self.left = binarySearchTree(val)

            # same steps as above here the condition we check is value to be inserted > currentNode's value
            else:
                if(self.right):
                    self.right.insert(val)
                else: self.right = binarySearchTree(val)

    def breadthFirstSearch(self):
        currentNode = self
        bfs_list = []
        queue = []
        queue.insert(0,currentNode)
        while(len(queue) > 0):
            currentNode = queue.pop()
            bfs_list.append(currentNode.val)
            if(currentNode.left):
                queue.insert(0,currentNode.left)
            if(currentNode.right):
                queue.insert(0,currentNode.right)

        return bfs_list

    # In order means first left child, then parent, at last right child
    def depthFirstSearch_INorder(self):
        return self.traverseInOrder([])

    # Pre order means first parent, then left child, at last right child
    def depthFirstSearch_PREorder(self):
        return self.traversePreOrder([])

    # Post order means first left child, then right child , at last parent
    def depthFirstSearch_POSTorder(self):
        return self.traversePostOrder([])

    def traverseInOrder(self, lst):
        if (self.left):
            self.left.traverseInOrder(lst)
        lst.append(self.val)
        if (self.right):
            self.right.traverseInOrder(lst)
        return lst

    def traversePreOrder(self, lst):
        lst.append(self.val)
        if (self.left):
            self.left.traversePreOrder(lst)
        if (self.right):
            self.right.traversePreOrder(lst)
        return lst

    def traversePostOrder(self, lst):
        if (self.left):
            self.left.traversePostOrder(lst)
        if (self.right):
            self.right.traversePostOrder(lst)
        lst.append(self.val)
        return lst

    def findNodeAndItsParent(self,val, parent = None):
        # returning the node and its parent so we can delete the node and reconstruct the tree from its parent
        if val == self.val: return self, parent
        if (val < self.val):
            if (self.left):
                return self.left.findNodeAndItsParent(val, self)
            else: return 'Not found'
        else:
            if (self.right):
                return  self.right.findNodeAndItsParent(val, self)
            else: return 'Not found'

    # deleteing a node means we have to rearrange some part of the tree
    def delete(self,val):
        # check if the value we want to delete is in the tree
        if(self.findNodeAndItsParent(val)=='Not found'): return 'Node is not in tree'
        # we get the node we want to delete and its parent-node from findNodeAndItsParent method
        deleteing_node, parent_node = self.findNodeAndItsParent(val)
        # check how many children nodes does the node we are going to delete have by traversePreOrder from the deleteing_node
        nodes_effected = deleteing_node.traversePreOrder([])
        # if len(nodes_effected)==1 means, the node to be deleted doesn't have any children
        # so we can just check from its parent node the position(left or right) of node we want to delete
        # and point the position to 'None' i.e node is deleted
        if (len(nodes_effected)==1):
            if (parent_node.left.val == deleteing_node.val) : parent_node.left = None
            else: parent_node.right = None
            return 'Succesfully deleted'
        # if len(nodes_effected) > 1 which means the node we are going to delete has 'children',
        # so the tree must be rearranged from the deleteing_node
        else:
            # if the node we want to delete doesn't have any parent means the node to be deleted is 'root' node
            if (parent_node == None):
                nodes_effected.remove(deleteing_node.val)
                # make the 'root' nodee i.e self value,left,right to None,
                # this means we need to implement a new tree again without the delted node
                self.left = None
                self.right = None
                self.val = None
                # construction of new tree
                for node in nodes_effected:
                    self.insert(node)
                return 'Succesfully deleted'

            # if the node we want to delete has a parent
            # traverse from parent_node
            nodes_effected = parent_node.traversePreOrder([])
            # deleting the node
            if (parent_node.left == deleteing_node) : parent_node.left = None
            else: parent_node.right = None
            # removeing the parent_node, deleteing_node and inserting the nodes_effected in the tree
            nodes_effected.remove(deleteing_node.val)
            nodes_effected.remove(parent_node.val)
            for node in nodes_effected:
                self.insert(node)

        return 'Successfully deleted'


bst = binarySearchTree()
bst.insert(7)
bst.insert(4)
bst.insert(9)
bst.insert(0)
bst.insert(5)
bst.insert(8)
bst.insert(13)

#          7
#        /  \
#      /     \
#     4        9
#    / \      /  \
#   0   5    8    13


print('IN order: ',bst.depthFirstSearch_INorder()) # useful in sorting the tree in ascending order
print('PRE order:' ,bst.depthFirstSearch_PREorder()) # pre order is useful in reconstructing a tree
print('POST order:', bst.depthFirstSearch_POSTorder()) # useful in finding the leaf nodes

print(bst.delete(5))
print(bst.delete(9))
print(bst.delete(7))

# after deleting
print('IN order: ',bst.depthFirstSearch_INorder())

''' Output
IN order:  [0, 4, 5, 7, 8, 9, 13]

PRE order: [7, 4, 0, 5, 9, 8, 13]

POST order: [0, 5, 4, 8, 13, 9, 7]

Successfully deleted
Successfully deleted
Successfully deleted

IN order:  [0, 4, 8, 13]
'''

Understanding Trees

Main Concepts

Tree Terminologies

Binary Trees

Set Implementation in Python

Reference