UNIT-2: Advanced Trees & Heaps

Dept. of AI

Advanced Data Structures

1. Advanced Trees
1. Extended Binary Tree
2. Threaded Binary Tree ( using In-order )

​

• Algebraic Expression
• Representation of Algebraic Expression
• Implementation of Algebraic Expression

​

• Binary Search Trees
• Definition of Binary Search Tree
• Binary Search Tree operations

​

• Heaps
• Heap Introduction
• Types of Heap ( Min heap and Max heap )

Topics

Dept. of AI

Extended Binary Tree:

​

An extended binary tree is a binary tree in which every node has either zero or two children. It means that in extended binary tree, all the NULL sub-trees of the original tree are replaced with special nodes called “external nodes” whereas other nodes are called “internal nodes”.

All external nodes are leaf nodes and the internal nodes are non-leaf nodes. They are also called as “Strict Binary Tree” or “Two-Tree”.

​

1. a) Extended Binary Tree

Dept. of AI

@ Extended Binary Tree

Threaded Binary Tree:

A threaded binary tree is a binary tree in which every node that does not have a right child has a thread (or link) to its In-order successor. By doing this threading we avoid the recursive method of traversing a tree. Moreover, half of the entries in the lift- child and right-child fields will contain NULL pointers.

These fields may be used more efficiently by replacing the NULL entries by Special pointers which points to nodes higher in the tree. Such types of special pointers are called “threads” and a binary tree with special pointers (threads) is called “threaded binary tree”.

1. b) Threaded Binary Tree

Dept. of AI

There are two types of threaded binary trees:

1. Single Threaded Binary Tree: A single threaded binary tree is a binary tree in which a NULL right pointer is made to point to the In-order successor.
2. Double Threaded Binary Tree: A double threaded binary tree is a binary tree in which both the left and right NULL pointers are made to point to the In-order predecessor and successor respectively.

Dept. of AI

In-order of the give binary tree:

1 4 7 11 20 23 24 30 34

Single Threaded Binary Tree

Double Threaded Binary Tree

( In-order predecessor and successor )

( In-order successor)

Example:

2. a) Representation of Algebraic Expressions

Dept. of AI

Algebraic Expressions: Algebraic expressions involve mathematical operations like addition, subtraction, multiplication, and division, typically with numerical values (constants or variables).

For example, Expression Tree for 3 + 4 * 2

​

• Infix: 3 + 4 * 2
• Postfix: 3 4 2 * +
• Prefix: + 3 * 4 2

 In this example:

• The root is the + operator.
• The left child is the operand 3.
• The right child is a multiplication (*) operation, which itself has operands 4 and 2.

+

/ \

3 *

/ \

4 2

Dept. of AI

Comparison of Expression Trees with Example

Construction of Infix to Expression Tree

​

In infix notation, operators are placed between operands. This is the most common way of writing arithmetic expressions. The construction process of Infix to Expression Tree is as follows:

Step 1: Start with the lowest precedence operator (if multiple operators are present) and make this operator the root of the tree.

Step 2: The left subtree is created from the part of the expression to the left of the operator, and the right subtree is created from the part of the expression to the right of the operator.

Step 3: Recursively apply this process to the left and right subexpressions

2. b) Implementation of Algebraic Expressions

Dept. of AI

Example: A + B * C

• The  + has a lower precedence than *, so + becomes the root.
• Operand A becomes the left child of +.
• The expression B*C becomes the right subtree. Since * has the highest precedence, it is the root of this subtree, and B and C are its children.

+

/ \

A *

/ \

B C

Construction of prefix to Expression Tree

​

In prefix notation, operators appear before their operands. The construction Process of Prefix to Expression Tree is as follows:

​

Step 1:  Start from the right of the prefix expression and push operands onto a stack.

Step 2:  When an operator is encountered, pop the required number of operands (2 for binary operators) from the stack, create a new node for the operator, and make the popped operands its children.

Step 3:  Push the new operator node back onto the stack.

Step 4:  At the end of the expression, the stack will contain a single node, which is the root of the expression tree.

Dept. of AI

Example: + A * B C

​

• Push ‘A’, ‘B’, and ‘C’ onto the stack.
• Pop ‘B’ and ‘B’, create a node with *, and push it back onto the stack.
• Pop ‘A’ and the * node, create a node with + and push it back onto the stack.
• The final stack contains the root of the tree.

+

/ \

A *

/ \

B C

Construction of postfix to Expression Tree

​

In postfix notation, operators are placed after their operands. The construction process of Postfix to Expression Tree is as follows:

​

Step 1: Start from the left of the postfix expression and push operands onto a stack.

Step 2: When an operator is encountered, pop the required number of operands (2 for binary operators) from the stack, create a new node for the operator, and make the popped operands its children.

Step 3: Push the new operator node back onto the stack.

Step 4: At the end of the expression, the stack will contain a single node, which is the root of the expression tree.

Dept. of AI

Example: A B C * +

• Push ‘A’, ‘B’, and ‘C’ onto the stack.
• Pop ‘B’ and ‘C’, create a node with *, and push it back onto the stack.
• Pop ‘A’ and the * node, create a node with + and push it back onto the stack.
• The final stack contains the root of the tree.

+

/ \

A *

/ \

B C

Dept. of AI

3. a) Binary Search Tree

What is Binary Search Tree?

• Binary search tree is a rooted binary tree data structure in which every node contains only smaller values in its left sub-tree and only larger values in its right sub-tree. BSTs are primarily used for efficient searching, insertion, and deletion of elements. For Examples, searching for a specific name in a phone book or finding a word in a dictionary. 
• The binary search tree is an advanced algorithm used for analyzing the node, its left and right branches, which are modeled in a tree structure and it enables faster lookups, insertions, and deletions of nodes. This makes the program really fast and accurate.
• Binary Search Tree (BST) is commonly utilized to implement complex searches, robust game logics, auto- complete activities, and graphics.

Note: We are considering that BSTs cannot contain duplicate Nodes.

Dept. of AI

For example, In the below tree, left sub-tree of every node contains nodes with smaller values and right sub-tree of every node contains larger values.

Dept. of AI

Given the root of a binary tree. Check whether it is a BST or not.

Example1: Input: root = [2, 1, 3, N, N, N, 5]

Output: true

Explanation: The left subtree of every node contains smaller keys and right subtree of every node contains greater keys. Hence, the tree is a BST.

Example2: Input: root = [2, N, 7, N, 6, N, 9]

Output: false

Explanation: Since the node to the right of node with key 7 has lesser key value, hence it is not a valid BST.

Example3: Input: root = [10, 5, 20, N, N, 9, 25]

Output: false

Explanation: The node with key 9 present in the right subtree has lesser key value than root node.

Dept. of AI

Scenario: Finding the smallest element 

Question: A user needs to quickly find the smallest element in a large dataset. They want to use a data structure that allows for efficient retrieval of the minimum value. Which data structure would be most suitable, and how would you implement it using a BST? 

​

Answer: A Binary Search Tree (BST) is an excellent choice for this scenario. The smallest element in a BST will always be the leftmost node. To find it, you would start at the root and repeatedly traverse to the left child until you reach a node with no left child. This node will be the smallest element in the BST. 

Scenario: Implementing a sorted dictionary 

Question: A software application needs to store a dictionary of words and their definitions, and it needs to be able to quickly look up words in alphabetical order. Which data structure is best suited for this task? 

​

Answer: A Binary Search Tree (BST) is well-suited for implementing a sorted dictionary. Because the BST is inherently sorted, you can easily traverse the nodes in ascending order to iterate through the dictionary alphabetically. The lookup of a word would also be efficient, as it leverages the BST's search properties. 

Dept. of AI

3. b) Binary Search Tree Operations

i) Insertion Operation in BST

In a binary search tree, the insertion operation is performed with O(log n) time complexity. In binary search tree, new node is always inserted as a leaf node.

The algorithm for insertion operation is as follows:

Step 1: Create a newNode with given value and set its left and right to NULL.

Step 2: Check whether tree is Empty.

Step 3: If the tree is Empty, then set root to newNode.

Step 4: If the tree is Not Empty, then check whether value of newNode is smaller or larger than the node (here it is root node).

Step 5: If newNode is smaller than or equal to the node, then move to its left child. If newNode is larger than the node, then move to its right child.

Step 6: Repeat the above step until we reach to a leaf node (reach to NULL).

Step 7: After reaching a leaf node, then insert the newNode as left child if newNode is smaller or equal to that leaf, else insert it as right child.

Dept. of AI

Example: Construct a Binary Search Tree (BST) for the following sequence of numbers- 50, 70, 60, 20, 90, 10, 40, 100

• Always consider the first element as the root node.
• Insert the given elements in the BST one by one:

This is a final Binary Search Tree.

Dept. of AI

Example-2: Construct a Binary Search Tree by inserting the following sequence of numbers:

10, 12, 5, 4, 20, 8, 7, 15 and 13

Above elements are inserted into a Binary Search Tree as follows:

This is a final Binary Search Tree.

Dept. of AI

ii) Deletion Operation in BST:

In a binary search tree, the deletion operation is performed with O(log n) time complexity. Deleting a node from Binary search tree has following three cases:

Case 1: Deleting a Leaf node (A node with no children)

Case 2: Deleting a node with one child

Case 3: Deleting a node with two children

Example: To delete a number (or Key) 20 from a Binary Search Tree with the following sequence of numbers: 15, 10, 20, 8, 12, 18, 30, 16 and 19.

Deleting a node with two children in a BST requires finding either the in-order successor (smallest node in the right subtree) or the in-order predecessor (largest node in the left subtree). 

The deletion process is as follows:

in-order: 8 10 12 15 16 18 19 20 30

In the given example, replace the node 20 to be deleted with its in-order predecessor 19, and then remove the predecessor from its original position. 

Dept. of AI

Scenario: Deleting a node with two children 

Question: A BST contains a node with both a left and right child that needs to be deleted. How would you handle this deletion to maintain the BST's properties? 

Answer: Deleting a node with two children in a BST requires finding either the in-order successor (smallest node in the right subtree) or the in-order predecessor (largest node in the left subtree). Replace the node to be deleted with its in-order successor or predecessor, and then remove the successor/predecessor from its original position. 

Dept. of AI

iii) Search Operation in BST:

In a binary search tree, the search operation is performed with O(log n) time complexity. The search operation is performed as follows:

Step 1: Read the search element from the user.

Step 2: Compare, the search element with the value of root node in the tree.

Step 3: If both are matching, then display "Given node found!!!" and terminate the function.

Step 4: If both are not matching, then check whether search element is smaller or larger than that node value.

Step 5: If search element is smaller, then continue the search process in left sub-tree.

Step 6: If search element is larger, then continue the search process in right sub-tree.

Step 7: Repeat the same until we found exact element or we completed with a leaf node.

Step 8: If we reach to the node with search value, then display "Element is found" and terminate the function.

Step 9: If we reach to a leaf node and it is also not matching, then display "Element not found" and terminate the function.

Dept. of AI

Example: To search a number (or Key) 16 in a Binary Search Tree with the following sequence of numbers:

15, 10, 20, 8, 12, 18, 25, 16, 19 and 30.

The Search process is as follows.

Dept. of AI

Scenario: Searching for an element in a BST 

Question: You need to efficiently search for a specific element (e.g., a user ID) within a large dataset stored in a BST. 

Answer: Start at the root of the BST. Compare the target element with the value of the current node. If they match, you've found it! If the target element is less than the current node's value, move to the left child; otherwise, move to the right child. Repeat this process until the element is found or you reach a leaf node (indicating the element is not in the tree). 

4 a) Heap Introduction

Heap: A heap is as special tree-based data structure in which the tree is a complete binary tree. Heap is a balanced binary tree data structure where the root node is compared with its children and arranged accordingly. A heap binary tree with N nodes has log N height.

Heaps are commonly used to implement priority queues, where the highest (or lowest) priority element is always at the root. For Example, heaps include scheduling tasks based on priority or finding the smallest or largest element in a data set. 

A Binary Heap Tree with following properties:

1. It’s a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.
2. A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be Minimum among all keys present in Binary Heap. In a Max Binary Heap, the key at root must be Maximum among all keys present in Binary Heap.

​

Dept. of AI

Dept. of AI

Min-Heap: In a Min-Heap the key present at the root node must be less than or equal among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree. In a Min-Heap the minimum key element present at the root.

Algorithm for Min Heap:

Step-1: Create a new node at the end of heap.

Step-2: Assign new value to the node.

Step-3: Compare the value of this child node with its parent.

Step-4: If value of parent is greater then child, then swap them.

Step-5: Repeat Step-3&4 unit heap property holds.

Example : Below is the Binary Tree that satisfies all the property of Min Heap

4 b) Heap Types

Dept. of AI

Example: Construct a Min Heap with the following data elements:

35 33 42 10 14 19 27 44 26 31

Dept. of AI

Max Heap: In a Max-Heap the key present at the root node must be greater than or equal among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree. In a Max-Heap the maximum key element present at the root.

Algorithm for Max Heap:

Step-1: Create a new node at the end of heap.

Step-2: Assign new value to the node.

Step-3: Compare the value of this child node with its parent.

Step-4: If value of parent is less then child, then swap them.

Step-5: Repeat Step - 3&4 unit heap property holds.

Example: Below is the Binary Tree that satisfies all the property of Max Heap

Dept. of AI

Example: Construct a Max heap with the following data elements (or items): 35 33 42 10 14 19 27 44 26 31

Dept. of AI