Tree and Binary Search tree

Tree and Binary search tree in data structure.
The complete explanation of working of trees and Binary Search Tree is given. It is discussed such a way that everyone can easily understand it. Trees have great role in the data structures.

1. TREES

2. Arrays
Linked Lists
172029 344830203429 304817
30 216 14 28 48
6 4814 21 28 30
Storing and modifying data
fast searching, slow insertion
slow searching, fast insertion
7

3. Hierarchically Structure

4. Trees
A tree is often used to represent a hierarchy .
Because the relationships between the items in the
hierarchy suggest the branches of a botanical tree.
For example, a tree-like organization chart is often
used to represent the lines of responsibility in a
business as shown in Figure

5. Trees

6. Trees
As we see in the figure, the tree is upside-down.
This is the usual way the data structure is drawn.
The president is called the root of the tree and the
clerks are the leaves.
A tree is extremely useful for certain kinds of
computations.
 For example, suppose we wish to determine the total
salaries paid to employees by division or by
department.
The total of the salaries in division A can be found by
computing the sum of the salaries paid in
departments A1 and A2 plus the salary of the vice-
president of division A.

7. Trees
 Similarly, the total of the salaries paid in
department A1 is the sum of the salaries of the
manager of department A1 and of the two clerks
below her.
Clearly, in order to compute all the totals, it is
necessary to consider the salary of every
employee.
Therefore, an implementation of this
computation must visit all the employees in the
tree.
An algorithm that systematically visits all the
items in a tree is called a tree traversal.

8. Trees in our life
Tree is an important data structure that
represent a hierarchy
Trees/hierarchies are very common in our life:
Tree of species(class/type) (is-a)
Component tree (part-of)
Family tree (parent-child)

9. 9
Tree Terminology
A tree is a collection of elements (nodes)
Each node may have 0 or more successors
(Unlike a list, which has 0 or 1 successor)
Each node has exactly one predecessor
Except the starting / top node, called the root
Links from node to its successors are called
branches
Successors of a node are called its children
Predecessor of a node is called its parent
Nodes with same parent are siblings
Nodes with no children are called leaves

10. 10
Owner
Jake
Manager Chef
Brad Carol
Waitress Waiter Cook Helper
Joyce Chris Max Len
A Tree Has a Root Node
ROOT NODE

11. 11
Owner
Jake
Manager Chef
Brad Carol
Waitress Waiter Cook Helper
Joyce Chris Max Len
Leaf nodes have no children
LEAF NODES

12. More Terminologies
Path
A sequence of edges
Length of a path
number of edges on the path
Depth/Level of a node
length of the unique path from the root to that node
Height of a node
length of the longest path from that node to a leaf
all leaves are at height 0
The height of a tree = the height of the root
= the depth of the deepest leaf
Ancestor and descendant
If there is a path from n1 to n2
n1 is an ancestor of n2, n2 is a descendant of n1
Proper ancestor and proper descendant

13. 13
Owner
Jake
Manager Chef
Brad Carol
Waitress Waiter Cook Helper
Joyce Chris Max Len
A Tree Has Levels
LEVEL 0

14. 14
Owner
Jake
Manager Chef
Brad Carol
Waitress Waiter Cook Helper
Joyce Chris Max Len
Level One
LEVEL 1

15. 15
Owner
Jake
Manager Chef
Brad Carol
Waitress Waiter Cook Helper
Joyce Chris Max Len
Level Two
LEVEL 2

16. 16
Representation Of a General Tree
-- first child/next sibling
Example for this tree:
A
B D
F G
H
E
C
A
null
First child
Next sibling
B
E
null
H
null null
C
null
D
null
F
null null
G
null
Cannot directly access D from A.
ParentPtr
Key value
sibling1st child

17. Tree Formal Definitions
A tree is a collection of nodes. The collection can be
empty,
Otherwise, a tree consists of a distinguished node r,
called the root, and zero or more (sub) trees T
1
, T
2
,.
……, T
k
, each of whose roots are connected by a
directed edge to r.
The root of each subtree is said to be a child of r and
r is the parent of each subtree root.

18. Binary Tree
The simplest form of tree is a binary tree. A binary tree
consists of
a.a node (called the root node) and
b.left and right sub-trees.
Both the sub-trees are themselves binary trees
We now have a recursively defined data structure.

19. Binary Tree

20. What is a binary tree?
Each node can have up to two successor
nodes (children)
The predecessor node of a node is called its parent
The "beginning" node is called the root (no parent)
A node without children is called a leaf

21. 21
Owner
Jake
Manager Chef
Brad Carol
Waitress Waiter Cook Helper
Joyce Chris Max Len
A Subtree
LEFT SUBTREE OF ROOT NODE

22. 22
Owner
Jake
Manager Chef
Brad Carol
Waitress Waiter Cook Helper
Joyce Chris Max Len
Another Subtree
RIGHT SUBTREE
OF ROOT NODE

23. Binary Trees
Some Binary Trees
One node
Two nodes
Three nodes

24. Convert a Generic Tree to a Binary
Tree

25. Binary Search Trees
Binary Search Tree Property: The value stored
at a node is greater than the value stored at its
left child and less than the value stored at its
right child.

27. Tree node structure
template<class ItemType>
class TreeNode {
ItemType info;
TreeNode* left;
TreeNode* right;
};

28. BinaryTree
Notation
In C++ the structure of binary tree
node can be specified as a
class named Node:
class Node{
public:
int key; // key stored in the node
Node *left; // link to left child
Node *right; // link to right child
};
parent
p[x]
Using pseudo code convention, the links are
defined as follows:
x -pointer to a node
left[x]- pointer to left child of x right[x]-
pointer to right child of x p[x]-pointer to
parent of x
key[x]-key stored in node x
x key
left[x] right[x]
left child right child

29. Function RetrieveItem

30. Function RetrieveItem
What is the base case(s)?
1)When the key is found
2)The tree is empty (key was not found)
What is the general case?
Search in the left or right subtrees

31. Binary Tree Traversal
Tree Traversal is the process of visiting each node in
the tree exactly one time.
Tree traversals are of two types
Depth First Traversal
Breadth First Traversal
The three Depth First Traversal techniques are
Preorder tree traversal
Inorder tree traversal
Postorder tree traversal

32. On a visit to node the data stored
·Preorder Tree Traversal
is processed, printed, etc.
A
1
In preorder traversal first the root is visited, then left subtree is visited
preorder , and finally the right subtree is visited preorder. B C
2
Preorder: A B C
A
·Inorder Tree Traversal
In inorder traversal first left subtree is visited inorder then root
is visited and finally the right subtree is visited inorder .
2
1
B C
Inorder: B A C
2A
·Postorder Tree Traversal
In postorder traversal first the left subtree is visited post order,
then right subtree is visited postorder, and finally root is visited .B C
1
Postorder:
B C A
In tree traversal each node is visited once only. Traversal is also referred to as walk.
The standard procedures of traversing a tree are known as preorder, inorder, and
postorder.
Binary Tree Traversal

33. BinaryTreeTraversal
Euler Tour
Euler tour traversal of binary tree is a path around the tree
.
Tour starts from the root toward the left child. The tree edges are kept
to the left . Each node is encountered three times: from left, from below
and from right
Postorder lists nodes on left of Euler path. Inorder lists nodes above the path
Postorder lists nodes on the right.

34. TreeTraversal
Recursive Algorithms
The recursive procedures for tree traversal use
recursive functions. Initially, the pointer to the
root is passed as argument to the function.
POSTORDER(x)
1 if x ≠ nil
2 then POSTORDER(left[x]) ► Traverse left subtree
postorder
3 POSTORDER(right[x]) ► Traverse right subtree postorder
4 print key[x] ►Print key
INORDER(x)
1 if x ≠ nil
2 then INORDER(left[x])► Traverse left subtree inorder
3 print key[x]► Print the key
4 INORDER(right[x]) ►Traverse right subtree inorder
PREORDER(x)
1 if x ≠ nil
2 then print key[x] ► Print key
3 PREORDER(left[x]) ► Traverse left subtree preorder
4 PREORDER(right[x]) ►Traverse right subtree preorder

35. InorderTree Traversal
Iterative Algorithm
The iterative procedure uses a stack to hold addresses of the
nodes waiting to be processed in traversal order. It includes
following steps:
Step #1:Push address of root on to the stack.
Step #2: Traverse the leftmost path of the, pushing the address of each node on to the
stack, and stopping when a leaf is reached.
Step #3: Pop the stack, and process the popped off node.
Step #4: If null is popped, exit, otherwise proceed to next step.
Step#5: If a right child of the processed node exists, push its address to stack.
Step#6: Repeat step # 2

36. Inorder Traversal
Step#:1Stack
Step#:2Stack
Step#:4
Step#:3
Step#:6
Step#:5
B
A
D
B
A
H
D
B
A
D
B
A
B
A
A

37. InorderTraversal-contd
Step#:8
Stack Stack
Step#:7
Step#:10
Step#:9
Step#:12
Step#:11
E
A
J
E
A
E
A
A
B
A
I
B
A

38. InorderTraversal-contd
Step#:13 Step#:14Stack
Stack
Step#:16
Step#:15
Step#:17 Step#:18
C
C
F
C
A

39. InorderTraversal:Example-contd
Step#:19
Step#:20Stack Stack
The inorder traversal of thesample binary tree is given by
H D I B J E A F C G
G

40. 40
Tree size
int TreeSize (root: TreePointer)
begin
if root==null //this is le ft/right child point of a le af
then return 0;
else
return 1 + TreeSize(root->left) + TreeSize(root->right);
end;
int TreeSize (root: TreePointer)
begin
if root==null //this is le ft/right child point of a le af
then return 0;
else
return 1 + TreeSize(root->left) + TreeSize(root->right);
end;
Size of a Node: the number of
descendants the node has (including
the node itself). The size of root is
the size of a tree. The size of a leaf is
1.

41. Properties of Binary Trees

A binary tree is a A binary tree is a fullfull binary tree if and only if: binary tree if and only if:
Each non leaf node has Each non leaf node has exactly twoexactly two child nodes child nodes
All leaf nodes lies at the same levelAll leaf nodes lies at the same level

It is called It is called fullfull since all possible node slots are since all possible node slots are
occupiedoccupied

42. COMPLETE BINARY TREE
A complete binary tree of depth d is the strictly binary
tree all of whose leaves are at level d.
A
CB
F
G
D
E
H
I
J
K
L
M
N O

43. ALMOST COMPLETE BINARY TREE
A binary tree of depth d is an almost binary tree if
–Any node n at level less than d - 1 has two sons
–For any node n in the tree with a right or left child at level I, the node must have left
child (if it has right child) and all the nodes on the left hand side of the node must have
two children.
Not an almost complete tree
Violate condition 1 Almost complete binary tree

44. A Full Binary Tree - Example

45. Complete Binary Trees - Example

B
B
A
A
C
C
D
D
E
E
H
H
I
I
J
J
K
K
F
F
G
G
Figure 13.8 A complete binary treeFigure 13.8 A complete binary tree

46. Strictly Binary Trees
A binary tree in which every non-leaf node has non-
empty left and right sub-trees
 A strict binary tree with n leaves always contain 2n-1
nodes.
 Level of a node = depth of a node

47. Almost Complete Binary Tree
A binary tree of depth d is an almost complete
binary tree if
Any node n at level less than d - 1 has two sons
(complete tree until level d-1)
For any node n in the tree with a right or left child
at level d, the node must have left child (if it has
right child) and all the nodes on the left hand side
of the node must have two children.

48. Almost Complete Binary Tree
Examples:
Not an almost complete tree
Violate condition 1
Not an almost complete tree
Violate condition 2

49. Almost Complete Binary Tree
Almost complete binary tree
1
2
3
4
5
6 7
8
9
Almost complete binary tree
but not strictly binary tree
7
1
2 3
4
5 6
8 9
10
Numbering of an almost complete binary tree

50. Numbering of an Almost
Complete Binary Tree
Almost complete binary tree
1
2
3
4
5
6 7
8
9
Almost complete binary tree
but not strictly binary tree
1
2 3
4
5 6 7
8 9
10
n nodes of an almost complete binary tree can be numbered from 1 to n

51. Function
Insert Item
Use the
binary
search tree
property to
insert the
new item at
the correct
place

52. Function
InsertItem
(cont.)
•Implementing
insertion using
recursion
Insert 11

53. What is the base case(s)?
The tree is empty
What is the general case?
Choose the left or right subtree
Function InsertItem (cont.)

54. template<class ItemType>
void TreeType<ItemType>::InsertItem(ItemType item)
{
Insert(root, item);
}

template<class ItemType>
void Insert(TreeNode<ItemType>*& tree, ItemType item)
{
if(tree == NULL) { // base case
tree = new TreeNode<ItemType>;
tree->info = item;
}
else if(item < tree->info)
Insert(tree->left, item);
else
Insert(tree->right, item);
}
Function InsertItem (cont.)

55. Binary Tree Traversal
Breadth First Tree Traversal
Implementation of this kind of traversal is
straightforward when a queue is used.
Consider a top down left-to-right, breadth first
traversal.
After a node is visited, its children, if any are
placed at the end of a queue, and the node at
the beginning of the queue is visited.

56. Breadth First Traversal
Example
A
C
D
B
E
F
G
I
H

57. Breadth First Traversal
Example
C
Queue
B
H
A
C
D
B
E
F
G
I
A

58. Breadth First Traversal
Example
Dqueue C
B
H
A
C
D
B
E
F
G
I
AC

59. Breadth First Traversal
Example
B
Enqueu D
D
H
A
C
D
B
E
F
G
I
AC

60. Breadth First Traversal
Example
Dqueue B
D
H
A
C
D
B
E
F
G
I
ACB

61. Breadth First Traversal
Example
D
Enqueue E, H
EH
H
A
C
D
B
E
F
G
I
ACB

62. Breadth First Traversal
Example
Dqueue D
EH
H
A
C
D
B
E
F
G
I
ACBD

63. Breadth First Traversal
Example
Dqueue E
H
H
A
C
D
B
E
F
G
I
ACBDE

64. Breadth First Traversal
Example
Enqueue F, G
HFG
H
A
C
D
B
E
F
G
I
ACBDE

65. Breadth First Traversal
Example
Dqueue H
FG
H
A
C
D
B
E
F
G
I
ACBDEH

66. Breadth First Traversal
Example
I
Enqueue I
FG
H
A
C
D
B
E
F
G
I
ACBDEH

67. Breadth First Traversal
Example
H
A
C
D
B
E
F
G
I
I
Dqueue F
G
ACBDEHF

68. Breadth First Traversal
Example
H
A
C
D
B
E
F
G
I
I
Dqueue G
ACBDEHFG

69. Breadth First Traversal
Example
H
A
C
D
B
E
F
G
I
Dqueue I
ACBDEHFGI

70. Simple Search Algorithm
Let us now state a simple search algorithm that will try to give you an
idea about the sort of data structures that will be used while searching,
and the stop criteria for your search. The strength of the algorithm is
such that we will be able to use this algorithm for both Depth First
Search (DFS) and Breadth First Search (BFS).
Let S be the start state
1. Initialize Q with the start node Q=(S) as the only entry; set Visited =
(S)
2. If Q is empty, fail. Else pick node X from Q
3. If X is a goal, return X, we’ve reached the goal
4. (Otherwise) Remove X from Q
5. Find all the children of state X not in Visited
6. Add these to Q; Add Children of X to Visited
7. Go to Step 2

71. Simple Search Algorithm
Here Q represents a priority queue. The algorithm is
simple and doesn’t need much explanation. We will use
this algorithm to implement blind and uninformed
searches. The algorithm however can be used to
implement informed searches as well.

72. Simple Search Algorithm Applied
to Depth First Search
Depth First Search dives into a tree deeper and
deeper to fine the goal state.
As mentioned previously we will give priority to
the element with minimum P(n) hence the node
with the largest value of height will be at the
maximum priority to be picked from Q. The
following sequence of diagrams will show you
how DFS works on a tree using the Simple
Search Algorithm.

73. We start with a tree containing nodes S, A, B, C, D, E, F, G, and H, with H as
the goal node. In the bottom left table we show the two queues Q and
Visited. According to the Simple Search Algorithm, we initialize Q with the
start node S,

74. •If Q is not empty, pick the node X with the minimum P(n) (in this case S), as it is
•the only node in Q. Check if X is goal, (in this case X is not the goal). Hence find
•all the children of X not in Visited and add them to Q and Visited. Goto Step 2.
Again check if Q is not empty, pick the node X with the minimum P(n) (in
this case either A or B), as both of them have the same value for P(n).
Check if X is goal, (in this case A is not the goal). Hence, find all the
children of A not in Visited and add them to Q and Visited. Go to Step 2.

75. Go on following the steps in the Simple Search Algorithm till you find a
goal node.
The diagrams below show you how the algorithm proceeds.

76. Here, from the 5th row of the table when we remove H and check if it’s the
goal, the algorithm says YES and hence we return H as we have reached
the goal state.

77. The diagram below also shows that DFS didn’t have to search the
entire search space, rather only by traveling in half the tree, the
algorithm was able to search the solution.

78. Simple Search Algorithm Applied
to Breadth First Search
Self study

79. Problems with DFS and BFS
????

80. BinarySearchTrees

81. BinarySearchTree
Definition
A binary search tree (BST) is organized such that
key in a node is larger than any key in the left
subtree and smaller than any key in right subtree.
Iif x is pointer to a tree node then binary-search-tree propertyimplies
key[x] > key[ left[x] ]
key[x] < key[right[x]] for all x
In BST, nodes with duplicate keys are not allowed.
Binary Search Tree

82. BinarySearchTree
Operations
Common operations performed on binary search tree are :
·INSERT- Add a new node with a given key
·SEARCH-Search a node with a given key
·DELETE-Delete a node with a given key
·MAXIMUM-Find largest key in the tree or in a subtree
·MINIMUM-Find smallest key in the tree or in a subtree
·SUCCESSOR- Find a node with smallest key which larger than the key in given node
·TRAVERSE- Traverse tree inorder, preorder, or postorder

83. BinarySearchTree
Insertion-1
Inserting a new node with key 10 into a Binary Search Tree

84. BinarySearchTree
Insertion-2
Insertion key 10 compared with key in the root node. It is smaller .
Next, the left child is examined.

85. BinarySearchTree
Insertion-3
Insertion key 10 compared with key in the left child. It is smaller .
Next, the left child is examined.

86. BinarySearchTree
Insertion-4
Insertion key 10 compared with key in the left child . It is smaller .
Next, the left child is examined.

87. BinarySearchTree
Insertion-5
Insertion key 10 compared with key in the left child. It is larger .
Next, the right child is examined.

88. BinarySearchTree
Insertion-6
Insertion key 10 compared with key in the right child. It is smaller .
Next, the left child is examined.

89. BinarySearchTree
Insertion-7
Insertion key 10 compared with key in the left child. It is larger .
Next, the right child is examined.

90. BinarySearchTree
Insertion-8
Insertion key 10 compared with key in the right child. It is smaller .
Node with key 11 is a leaf. The new key is inserted as left child of the leaf
being examined

91. BinarySearch
Insertion-9
Tree
key 10is placed in new left child

92. BinarySearchTree
INSERT Method
The INSERT Method adds a new node. The pointer to new node is
passed as argument. to the insert method. Starting with root, the
input key is compared successively with left or right child until a leaf
is reached.. The link pointer of the leaf is reset to point to the new
node.
INSERT(T, z)► z is pointer to new node
1 y←NIL ► y is a temporary pointer used to track the parent
2 x←root[T]►x is another pointer to track current node. It is set initially to
point to root
3 while x ≠ NIL
4 do y←x
5 if key[z] <key[x]►Compare given key with the key in node being
examined
6 then x←left[x] ►If given key is smaller proceed to left child
7 else x←right[x] ►If given key is larger proceed to right child
8 p[z]←y ► y holds the pointer to parent of the node being examined
9 if y=NIL►The node being added is the first node ( has no parent)
10 then root[T] ← z
11 else if key[z] < key[y] ►Check whether new node to be added is left child or
right child
12 then left[y]←z ►If left child, reset the parent node pointer link to left
child
13 else right[y]←z►If right child reset parent node pointer to link to right child

93. BinarySearch
Searching -1
Binary tree is searched for node
with key=71
Tree

94. BinarySearchTree
Searching -2
Search key 71 is compared with the key in root. It is larger.
Next, the right child is examined

95. BinarySearchTree
Searching -3
Search key 71 is compared with the key 85 in right child. It is
smaller.
Next, the left child is examined

96. BinarySearchTree
Searching -4
Search key 71 is compared with the key 81 in left child. It is smaller.
Next, the left child is examined

97. BinarySearchTree
Searching -5
Search key 71 is compared with the key 68 in left child. It is larger.
Next, the right child is examined

98. BinarySearchTree
Searching -6
Search key 71 is compared with the key 76 in left child. It is smaller.
Next, the left child is examined

99. BinarySearch
Searching -7
Search key 71 matches. Search is successful.
Tree

100. BinarySearchTree
SEARCH Method
SEARCH(x, k)►x is pointer to root and k is given key
1 while x ≠ NIL and k ≠ key[x]► Loop until a match is found or a leaf is
reached
2 do if k < key[x]► Check if given key is smaller
3 then x←left[x]► Proceed to left child if key smaller
4 else x←right[x]► Proceed to right child if key is larger
5 return x►Return NIL if no match found and pointer to node with matched
key
The SEARCH method finds a node with a given key. The search
procedure starts with the root. It successively compares keys in
the left or right children, depending on whether the key in the
parent node is larger or smaller than the given key. The search
terminates when either a matching key is found, or a leaf is
reached. The method returns a pointer to the node which has the
matching key or null pointer if no match is found..

101. BinarySearchTree
Smallest Key
The smallest key is found by starting with root
node and traversing leftmost path of BST

102. BinarySearchTree
Minimum key in a Subtree
The minimum key is found by starting with root nodeof the subtreeand
traversing leftmost path ofin the subtree

103. BinarySearchTree
MINIMUM Method
The MINIMUM method finds the smallest key in a binary
search tree or in any of the subtrees. It starts with the root
,or root of subtree, and proceeds down the leftmost path in
the tree or subtree.
The procedure returns pointer to the node with the smallest key.
MINIMUM(x)►x is pointer to root, or root of the subtree
1 whileleft[x] ≠ NIL►Move down the leftmost path until
leaf is reached
2 do x ←left[x] ►Move to left child
3 return x►Return pointer to the leaf , which contains the smallest
key

104. BinarySearchTree
Largest Key
The largest key is found by starting with root node and
traversing rightmost path of BST

105. BinarySearchTree
Maximum Key in a Subtree
The maximum key is found by starting with root nodeof the subtreeand
traversing rightmost path ofin the subtree

106. BinarySearchTree
MAXIMUM Method
The MAXIMUM method finds the largest key in a binary
search tree or in any of the subtrees.It starts with the root ,or
root of subtree, and proceeds down the rightmost path in the
tree or subtree.
The procedure returns pointer to the node with the largest key.
MAXIMUM(x)►x is pointer to root or root of the subtree
1 whileright[x] ≠ NIL►Move down the rightmost path
until leaf is reached
2 do x ←right[x] ►Move to right child
3 return x►Return pointer to the leaf , which contains the
largest key

107. BinarySearchTree
Deleting
a leaf node
LeafNode-1
Node with key 73 is

108. BinarySearchTree
Deleting Leaf Node -2
First, the node with key 73 is searched. The key 73 is compared
successively with keys 38, 82,47,62,75 until it matches with key in
a node. The search path is highlighted

109. BinarySearchTree
Deleting Leaf Node-3
Node with key 73 is de-linked from the parent node with
key 75, by setting the left link-pointer in parent node to
null

110. BinarySearchTree
Deleting Leaf Node-4
Finally, the de-linked node with key 73 is
removed

111. BinarySearchTree
Deleting Node With SingleChild-1
Node with key 7has a single left child with key 22

112. BinarySearchTree
Deleting Node With Single Child-2
First, the node with key 7 is searched. The key is compared
successively with keys 38,25,and 6, until a match is found The
search path is highlighted. The sub-tree, rooted at the node to be
deleted, is shown in yellow shade.

113. BinarySearchTree
Deleting Node With Single Child-3
The node to be deleted with key 7, is de-linked from its parent
node with key 6 and its right child with key 22
The right child link-pointer of parent node with key 6, is reset
to point to the node with key 22

114. BinarySearchTree
The de-linked node with key 7 is removed
Deleting Node With SingleChild-4

115. BinarySearchTree
The BST after node with 7 has been removed
Deleting Node With SingleChild-5

116. BinarySearchTree
Deleting Node With Both Children-1
The node with key 33 is to be deleted. It
keys 32 and 41.
has both left and right children with

117. BinarySearchTree
Deleting Node With Both Children-2
First, the node with key 33 is searched. The key 33 is successively
compared with the keys 47 and 25 until a match is found. The
search path is highlighted.

118. BinarySearchTree
Deleting Node With Both Children-3
In order to delete the node, its in-order successor is searched, which
contains smallest of all the keys contained in the right sub-tree. Sub-
tree is traversed by following the leftmost path, beginning with sub-
tree node with .The search path is shown in yellow shade.
Thein-order successorof node with key 33 is the node with key 34.

119. BinarySearchTree
Deleting Node WithBoth Children-4
in the node that contains key 33.The key34 of in-order successor isto be copied

120. BinarySearchTree
Deleting Node With Both Children-5
The in-order successor with key 34is de-linked from its parent node with key 38.

121. BinarySearchTree
Deleting Node Both Children-6
The key 34 in the in-order successor
The in-order successor is deleted.
is copied into the node that holds key 33.

122. BinarySearchTree
Deleting Node Both Children-7
The node with key 33 is removed. The BST
property is preserved.

123. BinarySearchTree
SUCCESSOR Method
SUCCESSOR(x)►x is pointer to given node
1 If right[x] ≠ NIL►If right subtree exists,then return pointer to node
with smallest key
2 then return MINUMUM(x)
3 y ←p[x] ►Proceed upward to parentnode
4 while y ≠ NIL and x=right[y] ►Continue until root is reached, or else a
node with left child is found
5 do x ← y
6 y← p[y]► Move to parent node
7 return y► Return pointer to the successor node
The SUCCESSOR method finds the inorder successor of a node with given key. If the right
subtree of the node exists, then the method finds the smallest key in the subtree. If the right
subtree does not exist, then the method proceeds upward until an ancestor with a node with
a left child of its parent is encountered.. It returns pointer to the successor node.

124. BinarySearchTree
DELETE Method
DELETE(T, z)
1 if left[z]=NIL or right[z]=NIL►Check if node has no left or right child
2 then y ← z ►if left or right child exists then y holds pointer to current node
3 else y ← SUCCESSOR(z) ►otherwise, y holds pointer to the successor node
4 if left[y] ≠ NIL► check if the left child exists
5 then x← left[x]►if so, move to left child
6 else x← right[y] ►otherwise, move to right child
7 if x ≠ NIL
8 then p[x] ← p[y] ► Set pointer of parent node
9 if p[y]=NIL
10 then root[T]← x
11 else if y=left[[p[y]] ►Set pointer of the parent to point to grand parent
12 then left[p[y]]←x
13 else right[p[y]] ←x
14 if y≠ z
15 then key[z]←key[y] ► Copy key of successor node
16 return y
The DELETE method removes a node with given key. After deletion, the tree is restructured
so that the binary-search-tree property is restored. The method deals with three cases(1)
node is a leaf (2) Node is not a leaf and has one child (3) Node is not a leaf ,and has two
children