Data structures and

Algorithms
Day School 4
Shalini Rajasingham
Introduction to Binary Trees
• Definition of a Binary Tree: A binary tree is a tree data structure in
which each node has at most two children, referred to as the left
child and the right child.
• Basic Properties:
• Each node contains a key (value), a pointer to the left child, and a pointer to
the right child.
• The topmost node is called the root of the tree.
• A binary tree can be empty (null).
Terminology
• Node: The basic unit of a binary tree, containing data and pointers to child
nodes.
• Edge: The link between parent and child nodes.
• Root: The topmost node in a tree, with no parent.
• Leaf: A node with no children.
• Parent: A node that has one or more children.
• Child: A node that has a parent node.
• Sibling: Nodes that share the same parent.
• Depth: The number of edges from the root to a node.
• Height: The number of edges on the longest path from a node to a leaf.
• Level: The depth of a node + 1 (the root is at level 1).
 Full and Complete Binary Tree

• Full Binary Tree Or Strict Binary:

• A full binary tree is a binary tree
in which all of the nodes have
either 0 or 2 offspring. In other
terms, a full binary tree is a binary
tree in which all nodes, except the
leaf nodes, have two offspring.
• every node has either two
children or no children at all.

•Complete Binary Tree

• The leftmost side of the leaf node
must always be filled first.
• It isn’t necessary for the last leaf
node to have a right sibling.
Height and Depth of a node in a Binary Tree
• Given a Binary Tree consisting of N nodes and a integer K, the task
is to find the depth and height of the node with value K in the
Binary Tree.
• The depth of a node is the number of edges present in path from the root
node of a tree to that node.
• The height of a node is the number of edges present in the longest path
connecting that node to a leaf node.
Examples
Binary Tree Representation
• Linked List Representation
• Structure: Each node is represented as an object with three fields: data, left
child pointer, and right child pointer.
• Advantages: Dynamic size, easy to insert and delete nodes.
• Disadvantages: Extra memory for pointers, no random access.
Binary Tree Representation
• Array Representation
• Structure: Nodes are stored in an array, with the root at index 0. For a
node at index i, its left child is at index 2i + 1 and its right child is at
index 2i + 2.
• Advantages: Space-efficient for complete binary trees, easy to navigate to
parent or child nodes.
• Disadvantages: Wasteful for sparse trees, resizing can be expensive.
Binary Tree Traversals
• A Tree Data Structure can be traversed in following ways:
• Depth First Search or DFS
• Inorder Traversal
• Preorder Traversal
• Postorder Traversal
• Level Order Traversal or Breadth First Search or BFS
• Boundary Traversal
• Diagonal Traversal
Inorder Traversal
• Algorithm Inorder(tree)
• Traverse the left subtree, i.e.,
call Inorder(left->subtree)
• Visit the root.
• Traverse the right subtree, i.e.,
call Inorder(right->subtree)
• Inorder traversal of binary tree
is
Preorder Traversal:
• Algorithm Preorder(tree)
• Visit the root.
• Traverse the left subtree,
i.e., call Preorder(left-
>subtree)
• Traverse the right subtree,
i.e., call Preorder(right-
>subtree)
Postorder Traversal:
• Algorithm Postorder(tree)
• Traverse the left subtree,
i.e., call Postorder(left-
>subtree)
1.Traverse the right subtree,
i.e., call Postorder(right-
>subtree)
2.Visit the root
Introduction to Binary Search Trees
• A Binary Search Tree is a data structure used in computer science for
organizing and storing data in a sorted manner.
• Each node in a Binary Search Tree has at most two children, a left
child and a right child, with the left child containing values less than
the parent node and the right child containing values greater than
the parent node.
• This hierarchical structure allows for efficient searching, insertion, and
deletion operations on the data stored in the tree.
Search - BST
• To search for the number X, We start at the root.
• Then:
• Compare the value to be searched with the value of the root.
• If it’s equal we are done with the search if it’s smaller we know that we
need to go to the left subtree because in a binary search tree all the
elements in the left subtree are smaller and all the elements in the right
subtree are larger.
• Repeat the above step till no more traversal is possible
• If at any iteration, key is found, return True. Else False.
• Example
Insertion - BST
• A new key is always inserted at the leaf by •
maintaining the property of the binary search
tree.
• Start searching for a key from the root until
we hit a leaf node. Once a leaf node is found,
the new node is added as a child of the leaf
node.
• The below steps are followed while we try to
insert a node into a binary search tree:
• Check the value to be inserted (say X) with the
value of the current node (say val) we are in:
• If X is less than val move to the left subtree.
• Otherwise, move to the right subtree.
• Once the leaf node is reached, insert X to its right
or left based on the relation between X and the
leaf node’s value.
• Example
Delete BST
• The task is to delete a node in this BST, which can be broken
down into 3 scenarios
• Case 1. Delete a Leaf Node in BST
Delete BST
• Case 2. Delete a Node with Single Child in BST
• Deleting a single child node is also simple in BST. Copy the child to
the node and delete the node
Delete BST
• Case 3. Delete a Node with Both Children in BST
• Deleting a node with both children is not so simple. Here we have
to delete the node is such a way, that the resulting tree follows the
properties of a BST.
BST Limitations
• Unbalanced BST:
• Occurs when nodes are inserted in a way that causes the tree to become
highly skewed (e.g., inserting sorted elements).
• Can lead to poor performance, with operations approaching O(n) complexity.
• Impact on Performance:
• The efficiency of BST operations relies on the tree's height.
• An unbalanced tree can degrade performance, making it no better than a
linked list in the worst case.
Introduction to Heaps
• A Heap is a complete binary tree data structure
that satisfies the heap property:
• every node, the value of its children is less than or
equal to its own value.
Heaps are usually used to implement priority queues,
where the smallest (or largest) element is always at the
root of the tree.
• Max Heap and Min Heap
Max – Min Heap
• Max Heap: The root node contains the maximum value, and
the values decrease as you move down the tree.
• Min Heap: The root node contains the minimum value, and the
values increase as you move down the tree.
Heap Operations
• Insertion in a Heap:
• Add the new element at the end of the array (maintaining completeness).
• Move the element to its correct position by repeatedly swapping with its
parent if it violates the heap property.
• Deletion in a Heap:
• Remove the root element (max or min, depending on the heap type).
• Move the last element in the array and "bubble down" to maintain the heap
property.
• Heapify: Converts an arbitrary binary tree into a heap.
Introduction to Priority Queues
• Definition and Properties:
• A priority queue is an abstract data type where each element has a priority
associated with it, and elements are served based on their priority (highest
priority elements are served first).
• Different from regular queues where elements are served in a first-come,
first-served manner.
• Comparison with Regular Queues:
• In regular queues, the order of elements is determined by the sequence in
which they arrive.
• In priority queues, the order is determined by the priority of the elements,
which can be independent of the arrival order.
Properties of Priority Queue
• So, a priority Queue is an extension of the queue with the
following properties.
• Every item has a priority associated with it.
• An element with high priority is dequeued before an element with low
priority.
• If two elements have the same priority, they are served according to their
order in the queue.
Implementing Priority Queues
• Using Arrays or Linked Lists:
• Simple implementation where elements are added at the end, and the
element with the highest priority is searched for and removed when needed.
• Not very efficient, especially for large datasets, as finding the highest priority
element requires scanning the entire structure.
• Using Heaps:
• A more efficient implementation using a heap data structure (usually a max
heap or min heap).
• Ensures that the highest (or lowest) priority element is always at the root and
can be accessed in constant time.
• Insertion and removal operations can be performed in logarithmic time.
Applications of Priority Queues
• Job Scheduling:
• In operating systems, priority queues are used to manage the execution of
processes based on their priority.
• Helps in implementing scheduling algorithms like Shortest Job First (SJF) or
Priority Scheduling.
• Dijkstra's Algorithm:
• A famous algorithm in graph theory used for finding the shortest path from a
starting node to all other nodes in a weighted graph.
• Priority queues are used to efficiently select the next node to explore based
on the shortest distance from the start.