Binary Tree

• The Binary tree means that the node can have maximum two children.
• Here, binary name itself suggests that 'two'; therefore, each node can have either 0, 1 or 2 children.

​

1

2

The above tree is a binary tree because each node contains the atmost two children. The logical representation of the above tree is given below:

3

• In the above tree, node 1 contains two pointers, i.e., left and a right pointer pointing to the left and right node respectively.
• The node 2 contains both the nodes (left and right node); therefore, it has two pointers (left and right).
• The nodes 3, 5 and 6 are the leaf nodes, so all these nodes contain NULL pointer on both left and right parts.

4

Properties of Binary Tree

• At each level of i, the maximum number of nodes is 2ⁱ.
• The height of the tree is defined as the longest path from the root node to the leaf node.
• The tree which is shown above has a height equal to 3.
• Therefore, the maximum number of nodes at height 3 is equal to (1+2+4+8) = 15.
• In general, the maximum number of nodes possible at height h is (2⁰ + 2¹ + 2²+….2^h) = 2^h+1 -1.
• The minimum number of nodes possible at height h is equal to h+1.
• If the number of nodes is minimum, then the height of the tree would be maximum.
• Conversely, if the number of nodes is maximum, then the height of the tree would be minimum.

​

5

• If there are 'n' number of nodes in the binary tree.
• The minimum height can be computed as:
• As we know that,
• n = 2^h+1 -1
• n+1 = 2^h+1
• Taking log on both the sides,
• log₂(n+1) = log₂ (2^h+1)
• log₂(n+1) = h+1
• h = log₂(n+1) - 1

​

​

6

• The maximum height can be computed as:
• As we know that,
• n = h+1
• h= n-1

​

7

Types of Binary Tree

• There are four types of Binary tree:
• Full/ proper/ strict Binary tree
• Complete Binary tree
• Perfect Binary tree
• Degenerate Binary tree
• Balanced Binary tree

​

8

 Full/ proper/ strict Binary tree

• The full binary tree is also known as a strict binary tree.
• The tree can only be considered as the full binary tree if each node must contain either 0 or 2 children.
• The full binary tree can also be defined as the tree in which each node must contain 2 children except the leaf nodes.

​

9

Properties of Full Binary Tree

• The number of leaf nodes is equal to the number of internal nodes plus 1.
• In the above example, the number of internal nodes is 5; therefore, the number of leaf nodes is equal to 6.
• The maximum number of nodes is the same as the number of nodes in the binary tree, i.e., 2^h+1-1.
• The minimum number of nodes in the full binary tree is 2*h-1.
• The minimum height of the full binary tree is log₂(n+1) - 1.
• The maximum height of the full binary tree can be computed as:
• n= 2*h - 1
• n+1 = 2*h
• h = n+1/2

​

10

• Complete Binary Tree
• The complete binary tree 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. In a complete binary tree, the nodes should be added from the left.
• Let's create a complete binary tree.

​

11

12

The above tree is a complete binary tree because all the nodes are completely filled, and all the nodes in the last level are added at the left first.

• Properties of Complete Binary Tree
• The maximum number of nodes in complete binary tree is 2^h+1 - 1.
• The minimum number of nodes in complete binary tree is 2^h.
• The minimum height of a complete binary tree is log₂(n+1) - 1.

​

13

• Perfect Binary Tree
• A tree is a perfect binary tree if all the internal nodes have 2 children, and all the leaf nodes are at the same level.

​

14

• The below tree is not a perfect binary tree because all the leaf nodes are not at the same level.

15

Degenerate Binary Tree

• The degenerate binary tree is a tree in which all the internal nodes have only one children.

16

• The above tree is a degenerate binary tree because all the nodes have only one child.
• It is also known as a right-skewed tree as all the nodes have a right child only.

17

• The above tree is also a degenerate binary tree because all the nodes have only one child. It is also known as a left-skewed tree as all the nodes have a left child only.

​

18

Balanced Binary Tree

• The balanced binary tree is a tree in which both the left and right trees differ by atmost 1.
• For example, AVL and Red-Black trees are balanced binary tree.

​

19

• The tree is a balanced binary tree because the difference between the left subtree and right subtree is zero.

20

21

The above tree is not a balanced binary tree because the difference between the left subtree and the right subtree is greater than 1.

Create Root

• We just create a Node class and add assign a value to the node. This becomes tree with only a root node.
• class Node:
• def __init__(self, data):
• self.left = None
• self.right = None
• self.data = data
• def PrintTree(self):
• print(self.data)
• root = Node(10)
• root.PrintTree()

22

• Output
• When the above code is executed, it produces the following result −
• 10

23

Inserting into a Tree

• To insert into a tree we use the same node class created above and add a insert class to it.
• The insert class compares the value of the node to the parent node and decides to add it as a left node or a right node.
• Finally the PrintTree class is used to print the tree.

​

24

• class Node:
• def __init__(self, data):
• self.left = None
• self.right = None
• self.data = data
• def insert(self, data):
• # Compare the new value with the parent node
• if self.data:
• if data < self.data:
• if self.left is None:
• self.left = Node(data)

25

• 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

​

26

• # Use the insert method to add nodes
• root = Node(12)
• root.insert(6)
• root.insert(14)
• root.insert(3)
• root.PrintTree()

27

Traversing a Tree

• The tree can be traversed by deciding on a sequence to visit each node.
• As we can clearly see we can start at a node then visit the left sub-tree first and right sub-tree next.
• Or we can also visit the right sub-tree first and left sub-tree next.
• Accordingly there are different names for these tree traversal methods.

28

Tree Traversal Algorithms

• Traversal is a process to visit all the nodes of a tree and may print their values too.
• Because, all nodes are connected via edges (links) we always start from the root (head) node.
• That is, we cannot randomly access a node in a tree. There are three ways which we use to traverse a tree.
• In-order Traversal
• Pre-order Traversal
• Post-order Traversal

​

29

In-order Traversal

• In this traversal method, the left subtree is visited first, then the root and later the right sub-tree.
• We should always remember that every node may represent a subtree itself.
• In the below python program, we use the Node class to create place holders for the root node as well as the left and right nodes.
• Then, we create an insert function to add data to the tree.
• Finally, the In-order traversal logic is implemented by creating an empty list and adding the left node first followed by the root or parent node.
• At last the left node is added to complete the In-order traversal.
• Please note that this process is repeated for each sub-tree until all the nodes are traversed.

​

30

• class Node:
• def __init__(self, data):
• self.left = None
• self.right = None
• self.data = data
• # Insert Node
• def insert(self, data):
• if self.data:
• if data < self.data:
• if self.left is None:
• self.left = Node(data)

31

• else:
• self.left.insert(data)
• else:
• if self.right is None:
• self.right = Node(data)
• else:
• self.right.insert(data)
• else:
• self.data = data

32

• # Print the Tree
• def PrintTree(self):
• if self.left:
• self.left.PrintTree()
• print( self.data)
• if self.right:
• self.right.PrintTree()

33

• # Inorder traversal
• # Left -> Root -> Right
• def inorderTraversal(self, root):
• res = []
• if root:
• res = self.inorderTraversal(root.left)
• res.append(root.data)
• res = res + self.inorderTraversal(root.right)
• return res

34

• root = Node(27)
• root.insert(14)
• root.insert(35)
• root.insert(10)
• root.insert(19)
• root.insert(31)
• root.insert(42)
• print(root.inorderTraversal(root))

35

• Output
• When the above code is executed, it produces the following result −
• [10, 14, 19, 27, 31, 35, 42]

36

Pre-order Traversal

• In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.
• In the below python program, we use the Node class to create place holders for the root node as well as the left and right nodes.
• Then, we create an insert function to add data to the tree.
• Finally, the Pre-order traversal logic is implemented by creating an empty list and adding the root node first followed by the left node.
• At last, the right node is added to complete the Pre-order traversal.
• Please note that, this process is repeated for each sub-tree until all the nodes are traversed.

​

37

• # Print the Tree
• def PrintTree(self):
• if self.left:
• self.left.PrintTree()
• print( self.data),
• if self.right:
• self.right.PrintTree()

38

• # Preorder traversal
• # Root -> Left ->Right
• def PreorderTraversal(self, root):
• res = []
• if root:
• res.append(root.data)
• res = res + self.PreorderTraversal(root.left)
• res = res + self.PreorderTraversal(root.right)
• return res

39

• Output
• When the above code is executed, it produces the following result −
• [27, 14, 10, 19, 35, 31, 42]

40

Post-order Traversal

• In this traversal method, the root node is visited last, hence the name.
• First, we traverse the left subtree, then the right subtree and finally the root node.
• In the below python program, we use the Node class to create place holders for the root node as well as the left and right nodes.
• Then, we create an insert function to add data to the tree.
• Finally, the Post-order traversal logic is implemented by creating an empty list and adding the left node first followed by the right node.
• At last the root or parent node is added to complete the Post-order traversal.
• Please note that, this process is repeated for each sub-tree until all the nodes are traversed.

​

41

• # Print the Tree
• def PrintTree(self):
• if self.left:
• self.left.PrintTree()
• print( self.data),
• if self.right:
• self.right.PrintTree()

42

• # Postorder traversal
• # Left ->Right -> Root
• def PostorderTraversal(self, root):
• res = []
• if root:
• res = self.PostorderTraversal(root.left)
• res = res + self.PostorderTraversal(root.right)
• res.append(root.data)
• return res

43

• Output
• When the above code is executed, it produces the following result −
• [10, 19, 14, 31, 42, 35, 27]

44

Why Binary Search Trees?

• In binary tree , we do not have any restriction on the nodes data.
• As a result, to search for an element we need to check both in left subtree and in right subtree.
• Due to this, the worst case complexity of search operation is O(n).
• Another variant of binary trees: Binary Search Trees (BSTs).
• The main use of this representation is for searching.
• In this representation we impose restriction on the nodes data.
• As a result, it reduces the worst case average search operation to O(logn).

45

Binary Search Tree Property

• In binary search trees, all the left subtree elements should be less than root data and the right subtree elements should be greater than root data. This is called binary search tree property.
• The left subtree of a node contains only nodes with keys less than the nodes key.
• The right subtree of a node contains only nodes with keys greater than the nodes key.
• Both the left and right subtrees must also be binary search trees.

46

Example

47

Example: The left tree is a binary search tree and the right tree is not a binary search tree (at node 6 it's not satisfying the binary search tree property).

Binary Search Tree Declaration

• There is no difference between regular binary tree declaration and binary search tree declaration.
• The difference is only in data but not in structure.

48

BST Declaration

class BSTNode:

def _init_ (self, data):

self.data = data

self.left= None

self. right = None

#set data

def setdata(self, data):

self.data = data

#get data

def getData(self):

return self.data

49

#get left child of a node

def getLeft(self):

return self.left

#get right child of a node

def getRight(self):

return self.right

50

Operations on Binary Search Trees

• Find/ Find Minimum / Find Maximum element in binary search trees
• Inserting an element in binary search trees
• Deleting an element from binary search trees

51

Finding an Element in Binary Search Trees

• Find operation is straight forward in a BST.
• Start with the root and keep moving left or right using the BST property.
• If the data we are searching is same as nodes data then we return current node.
• If the data we are searching is less than nodes data then search left subtree of current node;
• otherwise search right subtree of current node.
• If the data is not present, we end up in a NULL link.

52

def find(root,data):

currentNode=root

while currentNode is not None and data!=currentNode.getData()

if data>currentNode.getData():

currentNode=currentNode.getRight()

else:

currentNode=currentNode.getLeft()

return currentNode

Time Complexity: O(n), in worst case (when BST is a skew tree). Space Complexity: O(n), for recursive stack.

53

Finding Minimum Element in Binary Search Trees

• In BSTs, the minimum element is the left-most node.
• In the BST below, the minimum element is 4.

54

Finding Minimum Element in Binary Search Trees

def findMin(root):

currentNode=root

if currentNode.getLeft()==None:

return currentNode

else:

return findMin(currentNode.getLeft())

55

Non recursive version

def findMin(root):

currentNode=root

if currentNode.getLeft()==None:

return None

while currentNode.getLeft()!=None:

currentNode=currentNode.getLeft()

return currentNode

​

Time complexity is O(n) and Space complexity is O(1)

56

Finding Maximum Element in Binary Search Trees

• In BSTs, the maximum element is the right-most node.
• In the BST below, the maximum element is 16.

57

Finding Maximum Element in Binary Search Trees

def findMax(root):

currentNode=root

if currentNode.getRight()==None:

return currentNode

else:

return findMax(currentNode.getRight())

​

58

Non recursive version

def findMax(root):

currentNode=root

if currentNode.getRight()==None:

return None

while currentNode.getRight()!=None:

currentNode=currentNode.getRight()

return currentNode

​

Time complexity is O(n) and Space complexity is O(1)

59

Inserting an Element in Binary Search Tree

• To insert data into binary search tree, first we need to find the location for that element.
• We can find the location of insertion by following the same mechanism as that of find operation.
• While finding the location, if the data is already there then we can simply neglect and come out.
• Otherwise, insert data at the last location on the path traversed.

60

Inserting an Element from Binary Search Tree

• As an example let us consider the following tree. The dotted node indicates the element (5) to be inserted.
• To insert S, traverse the tree using find function.
• At node with key 4, we need to go right, but there is no subtree, so 5 is not in the tree, and this is the correct location for insertion.

​

61

Inserting an Element in Binary Search Tree

def insertNode(root,node):

if root is None:

root = node

else:

if root.data>node.data:

if root.left==None:

root.left=node

else:

insertNode(root.left,node)

else:

if root.right==None:

root.right=node

else:

insertNode(root.right,node)

Time Complexity:O(n). Space Complcxity:O(n). for recursive stack. For iterative version, space complexity is 0(1).

62

Deleting an Element from Binary Search Tree

• The delete operation is more complicated than other operations.
• In this operation also, first we need to find the location of the element which we want to delete.
• Once we have found the node to be deleted, consider the fol lowing cases:

63

Deleting an Element from Binary Search Tree

• If the element to be deleted is a leaf node: return NULL to its parent.
• That means make the corresponding child pointer NULL. In the tree below to delete 5, set NULL to its parent node 2.

64

Deleting an Element from Binary Search Tree

• If the element to be deleted has one child: In this case we just need to send the current node's child to its parent.
• In the tree below, lo delete 4, 4 left subtree is set to its parent node 2.

​

​

65

Deleting an Element from Binary Search Tree

• If the element to be deleted has both children:
• The general strategy is to replace the key of this node with the largest element of the left subtree and recursively delete that node (which is now empty).

​

66

Deleting an Element from Binary Search Tree

• In the tree below, to delete 8, it is the right child of the root. The key value is 8.
• It is replaced with the largest key in its left subtree (7), and then that node is deleted as before.

​

​

67

AVL (Adelson-Velskii and Landis) Trees

68

AVL (Adelson-Velskii and Landis) Trees

​

• In HB(k),if k = 1 (if balance factor is one), such a binary search tree is called an AVL tree.
• That means an AVL tree is a binary search tree with a balance condition: the difference between left subtree height and right subtree height is at most 1.

Properties of AVL Trees

• A binary tree is said to be an AVL tree, if;
• It is a binary search tree,
• For any node X, the height of left subtree of X and height of right subtree of X differ by at most 1.

69

Example

70

As an example, among the above binary search trees, the left one is not an AVL tree, whereas the right binary search tree is an AVL tree.

AVL Tree Declaration

• Since AVL tree is a BST, the declaration of AVL is similar to that of BST. But just to simplify the operations, we also include the height as part of the declaration.

class AVLNode:

def _init_(self,balancefactor,left,right):

self.data=data

self.balancefactor=0

self.left=left

self.right=right

71

Finding height of AVL Tree

def height(self):

return self.recHeight(self.root)

def recHeight(self,root):

if root==None:

return 0

else:

leftH=self.recHeight(r.left)

rightH=self.recHeight(r.right)

if leftH>rightH:

return 1+leftH

else:

retun 1+rightH

​

Time complexity is O(1)

72

Inserting an Element in AVL Tree

def insertNode(root,node):

if root is None:

root = node

else:

if root.data>node.data:

if root.left==None:

root.left=node

else:

insertNode(root.left,node)

73

Inserting an Element in AVL Tree

else:

if root.right==None:

root.right=node

else:

insertNode(root.right,node)

​

Time Complexity:O(n).

Space Complcxity:O(n). for recursive stack.

For iterative version, space complexity is 0(1).

74

Rotations

• When the tree structure changes (e.g., with insertion or deletion), we need to modify the tree to restore the AVL tree property.
• This can be done using single rotations or double rotations. Since an insertion/deletion involves adding/deleting a single node, this can only increase/decrease the height of a subtree by 1.

75

Rotations

• If the AVL tree property is violated at a node X, it means that the heights of left(X) and right(X) differ by exactly 2.
• Rotations is the technique used for restoring the AVL tree property.
• This means, we need to apply the rotations for the node X.

76

Types of Violations

1. An insertion into the left subtree of the left child of X.

2. An insertion into the right subtree of the left child of X.

3. An insertion into the left subtree of the right child of X.

4. An insertion into the right subtree of the right child of X.

77

• Cases 1 and 4 are symmetric and easily solved with single rotations.
• Similarly, cases 2 and 3 are also symmetric and can be solved with double rotations (needs two single rotations).

78

Single Rotations

• Left Left Rotation (LL Rotation) [Case-1]:
• The rotation does not have to be done at the root of a tree.
• In general, we start at the node inserted and travel up the tree, updating the balance information at every node on the path.

79

Single Rotations

80

For example, after the insertion of 7 in the original AVL tree on the left, node 9 becomes unbalanced.

So, we do a single left-left rotation at 9. As a result we get the tree on the right.

def singleLeftRotate(self,root):

w=root.left

root.left=w.right

w.right=root

return w

​

Time complexity is O(1)

Space complexity is O(1)

81

Right Right Rotation (RR Rotation)

• Right Right Rotation (RR Rotation) (Case-4]: In this case, node 15 is not satisfying the AVL tree property .

​

82

For example, after the insertion of 29 in the original AVL tree on the left, node 15 becomes unbalanced.

​

So, we do a single right-right rotation at 15. As a result we get the tree on the right.

def singleRightRotate(self,root):

w=root.right

root.right=w.left

w.left=root

return w

​

Time complexity is O(1)

Space complexity is O(1)

83

Double Rotations

• Left Right Rotation (LR Rotation) (Case-2): For case-2 and case-3 single rotation does not fix the problem.
• We need to perform two rotations.
• Insertion of 7 is creating the case 2 scenario.

84

• def rightLeftRotate(self,root):

x=root.left

if x.balanceFactor==-1:

root.balanceFactor=0

x.balanceFactor=0

root=self.singleLeftRotate(root)

else:

y=x.right

if y.balanceFactor==-1:

root.balanceFactor=1

x.balanaceFactor=0

85

elif y.balanceFactor==0

root.balanaceFactor=0

x.balanceFactor=0

else:

root.balanceFactor=0

x.balanceFactor=-1

y.balanceFactor=0

root.left=self.singleRightRotate(x)

root=self.singleLeftRotate(root)

return root

86

Right Left Rotation (RL Rotation)

• Right Left Rotation (RL Rotation) (Case -3): Similar to case-2, we need to perform two rotations to fix this scenario.
• The insertion of 5 is creating the casc-3 scenario.

87

• def rightLeftRotate(self,root):

x=root.right

if x.balanceFactor==-1:

root.balanceFactor=0

x.balanceFactor=0

root=self.singleRightRotate(root)

else:

y=x.left

if y.balanceFactor==-1:

root.balanceFactor=1

x.balanaceFactor=0

88

• elif

y.balanceFactor==0

root.balanaceFactor=0

x.balanceFactor=0

else:

root.balanceFactor=0

x.balanceFactor=-1

y.balanceFactor=0

root.right=self.singleLeftRotate(x)

root=self.singleRightRotate(root)

return root

89

Heap

• Heap is a special tree structure in which each parent node is less than or equal to its child node. Then it is called a Min Heap.
• If each parent node is greater than or equal to its child node then it is called a max heap.
• It is very useful in implementing priority queues where the queue item with higher weightage is given more priority in processing.

90

Create a Heap

• A heap is created by using python’s inbuilt library named heapq. This library has the relevant functions to carry out various operations on heap data structure. Below is a list of these functions.
• heapify − This function converts a regular list to a heap. In the resulting heap the smallest element gets pushed to the index position 0. But rest of the data elements are not necessarily sorted.
• heappush − This function adds an element to the heap without altering the current heap.
• heappop − This function returns the smallest data element from the heap.
• heapreplace − This function replaces the smallest data element with a new value supplied in the function.

​

91

• A heap is created by simply using a list of elements with the heapify function.
• In the below example we supply a list of elements and the heapify function rearranges the elements bringing the smallest element to the first position.

92

• import heapq
• H = [21,1,45,78,3,5]
• # Use heapify to rearrange the elements
• heapq.heapify(H)
• print(H)

93

• Output
• When the above code is executed, it produces the following result −

​

• [1, 3, 5, 78, 21, 45]

94

Inserting into heap

• Inserting a data element to a heap always adds the element at the last index.
• But you can apply heapify function again to bring the newly added element to the first index only if it smallest in value.
• In the below example we insert the number 8.

​

95

• import heapq
• H = [21,1,45,78,3,5]
• # Covert to a heap
• heapq.heapify(H)
• print(H)
• # Add element
• heapq.heappush(H,8)
• print(H)

96

• Output
• When the above code is executed, it produces the following result −

​

• [1, 3, 5, 78, 21, 45]
• [1, 3, 5, 78, 21, 45, 8]

97

Removing from heap

• You can remove the element at first index by using this function. In the below example the function will always remove the element at the index position 1.
• import heapq
• H = [21,1,45,78,3,5]
• # Create the heap
• heapq.heapify(H)
• print(H)
• # Remove element from the heap
• heapq.heappop(H)
• print(H)

98

• Output
• When the above code is executed, it produces the following result −

​

• [1, 3, 5, 78, 21, 45]
• [3, 21, 5, 78, 45]

99

Replacing in a Heap

• The heap replace function always removes the smallest element of the heap and inserts the new incoming element at some place not fixed by any order.
• import heapq
• H = [21,1,45,78,3,5]
• # Create the heap
• heapq.heapify(H)
• print(H)
• # Replace an element
• heapq.heapreplace(H,6)
• print(H)

100

• Output
• When the above code is executed, it produces the following result −

​

• [1, 3, 5, 78, 21, 45]
• [3, 6, 5, 78, 21, 45]

101

Multi way search trees

• The m-way search trees are multi-way trees which are generalised versions of binary trees where each node contains multiple elements.
• In an m-Way tree of order m, each node contains a maximum of m – 1 elements and m children.
• The goal of m-Way search tree of height h calls for O(h) no. of accesses for an insert/delete/retrieval operation.
• Hence, it ensures that the height h is close to log_m(n + 1).�The number of elements in an m-Way search tree of height h ranges from a minimum of h to a maximum of

102

• An m-Way search tree of n elements ranges from a minimum height of log_m(n+1) to a maximum of n.
• An example of a 5-Way search tree is shown in the figure below. Observe how each node has at most 5 child nodes & therefore has at most 4 keys contained in it. 

103

104

The structure of a node of an m-Way tree is given

• class node:
• def __init__(self):
• self.count = -1
• self.value = [-1]*(MAX + 1)
• self.child = [None]*(MAX + 1)
• Here, count represents the number of children that a particular node has.
• The values of a node stored in the array value
• The addresses of child nodes are stored in the child array
• The MAX macro signifies the maximum number of values that a particular node can contain.

​

​

105

Searching in an m-Way search tree

• Searching for a key in an m-Way search tree is similar to that of binary search tree.
• To search for 77 in the 5-Way search tree, shown in the figure, we begin at the root & as 77> 76> 44> 18, move to the fourth sub-tree.
• In the root node of the fourth sub-tree, 77< 80 & therefore we move to the first sub-tree of the node. Since 77 is available in the only node of this sub-tree, we claim 77 was successfully searched

​

106

107

• def search(val, root, pos):
• # if root is None then return
• if (root == None):
• return None
• else :
• # if node is found
• if (searchnode(val, root, pos)):
• return root
• # if not then search in child nodes
• else:
• return search(val, root.child[pos], pos)

​

108

# Searches the node

• def searchnode(val, n, pos):
• # if val is less than node.value[1]
• if (val < n.value[1]):
• pos = 0
• return 0

109

• # if the val is greater
• else :
• pos = n.count
• # check in the child array
• # for correct position
• while ((val < n.value[pos]) and pos > 1):
• pos-=1
• if (val == n.value[pos]):
• return 1
• else:
• return 0

110

search():

•  The function search() receives three parameters
• The first parameter is the value to be searched, second is the address of the node from where the search is to be performed and third is the address of a variable that is used to store the position of the value once found
• Initially a condition is checked whether the address of the node being searched is NULL

111

• If it is, then simply a NULL value is returned
• Otherwise, a function searchnode() is called which actually searches the given value
• If the search is successful the address of the node in which the value is found is returned
• If the search is unsuccessful then a recursive call is made to the search() function for the child of the current node

​

112

• searchnode(): 
• The function searchnode() receives three parameters
• The first parameter is the value that is to be searched
• The second parameter is the address of the node in which the search is to be performed and third is a pointer pos that holds the address of a variable in which the position of the value that once found is stored
• This function returns a value 0 if the search is unsuccessful and 1 if it is successful

​

113

• In this function initially it is checked whether the value that is to be searched is less than the very first value of the node
• If it is then it indicates that the value is not present in the current node.
• Hence, a value 0 is assigned in the variable that is pointed to by pos and 0 is returned, as the search is unsuccessful

​

114