Tree Data Structures
General Trees
Trees are a nonlinear Data Structure, compared to arrays, linked lists, stacks and queues which are linear data strcutures
class Node(object):
def __init__(self, data):
self.data = data
self.children = []
def add_child(self, obj):
self.children.append(obj)
Root = Node(1)
Red = Node(2)
Yellow = Node(3)
Pink_1 = Node(4)
Pink_2 = Node(5)
Pink_3 = Node(6)
Brown_2 = Node(7)
Brown_1 = Node(8)
Green_1 = Node(9)
Green_2 = Node(10)
Blue = Node(11)
Root.add_child(Red)
Root.add_child(Yellow)
Red.add_child(Pink_1)
Red.add_child(Pink_2)
Red.add_child(Pink_3)
Yellow.add_child(Brown_1)
Yellow.add_child(Brown_2)
Pink_1.add_child(Green_1)
Pink_1.add_child(Green_2)
Brown_2.add_child(Blue)
 Including the Height and Depth of a Tree
Binary Trees
A Binary Tree is a Tree data structure in which each node has at most two childern.
When we implement a binary tree each node has three attributes:
 Data
 Left Child
 Right Child.
class Node(object):
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree(object):
def __init__(self, root):
self.root = Node(root)
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)
tree.root.right.left = Node(6)
tree.root.right.right = Node(7)
Binary Tree Traversals
Tree Traversal is the Process of visiting (checking and/or updating) each node in a tree data structure, exactly once. Unliked other data structures, trees can be traversed in multiple ways.
DepthFirst or BreadthFirst Order
DepthFirst Order:
BreadthFirst Order (or Level Order Traversal)
Different Operations on Binary Trees:
Time Complexity of Different Operations in a Binary Tree
Operation  Running Time (Worst) 

Search  O(n) 
Delete  O(n) 
Insertion  O(n) 
Calculating Height of a Binary Tree
Calculating the Size of a Binary Tree
Insertion into a Regular Binary Tree
Deletion of a Node in a Regular Binary Tree
Implementing a Binary Tree
Coming Soon:
Binary Tree from an Array
Binary Tree from an Linked list
Binary Search Tree
A BST is a SPECIAL FORM of a Binary Tree data structure where each node has a comparable value, and smaller valued childern attached to left and larger valued childern attached to the right
Pros and Cons of a Binary Search Tree
Pros:
 Inserting and Deleting
 Speed of Access
 Maintains sorted order; retrieval of elements is in order
Cons:
 Expensive because of their creation and management
Binary Search Tree Introduction
Operations on Binary Search Tree:
Insertion into a Binary Search Tree
Deletion of a Node in a Binary Search Tree
Searching for a Value in a Binary Search Tree
Time Complexity of Different Operations of a Binary Search Tree
Operation  Average  Worst Case 

Space  O(n)  O(n) 
Search  O(log n)  O(n) 
Delete  O(log n)  O(n) 
Insertion  O(log n)  O(n) 
Coming Soon:
Rebalancing a Binary Search Tree by Rotation

Left Rotation

Right Rotation

Left Left Rotation

Right Right Rotation
AVL Tree
Operations on AVL Tree
 AVL Tree Search
Time Complexity of Different Operations of a AVL Tree
Operation  Average  Worst Case 

Space  O(n)  O(n) 
Search  O(log n)  O(log n) 
Delete  O(log n)  O(log n) 
Insertion  O(log n)  O(log n) 
Coming Soon ( End of 2021)
RedBlack Tree
 RedBlack Tree Introduction
Operations on RedBlack Tree

RedBlack Tree Insertion

RedBlack Tree Deletion

RedBlack Tree Search
Time Complexity of Different Operations of a RedBlack Tree
Operation  Average  Worst Case 

Space  O(n)  O(n) 
Search  O(log n)  O(log n) 
Delete  O(log n)  O(log n) 
Insertion  O(log n)  O(log n) 
Splay Tree
 Splay Tree Introduction
Operations on a Splay Tree

Splay Tree Insertion

Splay Tree Deletion

Splay Tree Search
Time Complexity of Different Operations of a Splay Tree
Operation  Average  Worst Case 

Space  O(n)  O(n) 
Search  O(log n)  O(log n) 
Delete  O(log n)  O(log n) 
Insertion  O(log n)  O(log n) 
Treap
 Treap Tree Introduction
Operations on a Treap

Treap Tree Insertion

Treap Tree Deletion

Treap Tree Search
Time Complexity of Different Operations of a Treap
Operation  Average  Worst Case 

Space  O(n)  O(n) 
Search  O(log n)  O(n) 
Delete  O(log n)  O(n) 
Insertion  O(log n)  O(n) 
BTree
 BTree Introduction
Operations on a BTree

BTree Insertion

BTree Deletion

BTree Search
Time Complexity of Different Operations of a BTree
Operation  Average  Worst Case 

Space  O(n)  O(n) 
Search  O(log n)  O(log n) 
Delete  O(log n)  O(log n) 
Insertion  O(log n)  O(log n) 