Data Structures - I
“No Bonus” marks for this course anymore
CP
CS
20
4
O my Lord! Expand for me my chest [with
assurance] and ease for me my task and untie
the knot from my tongue that they may
understand my speech. (Quran 20 : 25-28)
1 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP
CS
20
4 Binary Search Tree
(BST)
Implementation
2 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Binary Search Tree – Node Class
CS public class intBSTnode {
20 public int data;
public intBSTnode left;
4 public intBSTnode right;
public intBSTnode () {
left = right = null;
}
public intBSTnode (int i) {
this(i, null, null);
}
public intBSTnode (int i, intBSTnode n, intBSTnode p)
{
data = i;
left = n;
right = p;
}
}
3 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Class – BinarySearchTree
CS public class BinarySearchTree {
20 private intBSTnode root;
4 // Constructor
public BinarySearchTree() {
root = null;
}
// All methods will be written here
}
4 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP
CS
20
4
Binary Search Tree
Operations
5 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST - Operations
CS
• Traversal
20 o Accessing/visiting all values of a tree once
4 • Searching
o Finding a key value
• Insertion
o Adding a value in a tree
• Deletion
o Removing a value from tree
• Creation
o Creating a tree from empty tree
6 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST - Traversal
CS
20
4 • Pre Order Traversal
• In Order Traversal
• Post Order Traversal
• Depth First Search
• Breadth First Search
7 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Post Order
CS
• Left - Right - Root
20
4 • the root is visited after both the left and
right sub trees
public void postorder (intBSTnode p) {
if (p != NULL) {
postorder(p.left);
postorder(p.right);
System.out.print(p.data + “ ”);
}
}
8 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP
CS
20
4
Binary Search Tree
Searching
(Iterative Solution)
9 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Searching -Iterative
CS public intBSTnode (int key) {
20 intBSTnode current = root;
while (current.data != key) {
4 if (key < current.data)
current = current.left;
else
current = current.right;
if (current == null);
return null;
}
return current;
}
10 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Searching - Tracing
CS
public intBSTnode find(int key) {
intBSTnode current = root; root
20if (current.data
while != key) {
(key < current.data)
4 elsecurrent = current.left;
current = current.right;
if (current == null);
return null;
}
return current;
}
11 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP
CS
20
4
Binary Search Tree
Searching
(Recursive Solution)
12 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Searching -Recursive
CS public boolean recurSearch(intBSTnode p, int data) {
20 if (p == null)
return(false);
4 if (data == p.data)
return(true);
else if (data < p.data)
return(recurSearch(p.left, data));
else
return(recurSearch(p.right, data));
}
13 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
public boolean recurSearch(intBSTnode p, int data) {
CP BST – Searching - Recursive
if (p == null) {
}
return(false);
CS
if (data == p.data) {
return(true); root
20
}
else if (data < p.data) {
return(recurSearch(p.left, data));
}4
else {
return(recurSearch(p.right, data));
}
}
14 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP
CS
20
4
Binary Search Tree
Insertion
15 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Insertion
CS public intBSTnode insert(intBSTnode p, int data)
20 {
if (p == null) {
4 }
p = new intBSTnode(data);
else {
if (data < p.data) {
p.left = insert(p.left, data);
}
else {
p.right = insert(p.right, data);
}
}
return p;
}
16 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Insertion - Tracing
CS
public intBSTnode insert(intBSTnode p, int data) {
if (p == null) { root
20
}
p = new intBSTnode(data);
else {
4 if (data < p.data) {
p.left = insert(p.left, data);
}
else {
p.right = insert(p.right, data);
}
}
return p;
}
17 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP
CS
20
4
Binary Search Tree
Deletion
18 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Deletion
CS
• Find node to be deleted
20
4 • Find Parent of node
• Check node is a “leaf”
• Has only Left Child
• Has only Right Child
• Find Smallest node
• Find Largest node
19 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Deletion - Find Node to Delete
CS public BSTnode findNode(int data) {
20 }
return findNode(root, data);
4 private BSTnode findNode(BSTnode p, int data) {
if (p == null)
return null;
else {
if (data == p.getData())
return p;
else if (data <p.getData())
return findNode(p.getLeft(),
data);
else
return findNode(p.getRight(),
data);
}
20 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
}
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Deletion – Find Node to Delete
CS public BSTnode findNode(int data) {
}
return findNode(root, data);
20 private BSTnode findNode(BSTnode p, int data) {
if (p == null)
4
return null;
else {
if (data == p.getData())
return p;
else if (data <p.getData())
return findNode(p.getLeft(), data); 59
else
return findNode(p.getRight(), data);
}
}
18 67
13 32 63 72
10 15 25 43
21 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Deletion - Find Parent Node
CS public BSTnode parent(BSTnode p) {
20 }
return parent(root, p);
4 private BSTnode parent(BSTnode root, BSTnode p) {
if (root == null || root == p)
return null;
if (root.getLeft()==p || root.getRight()==p)
return root;
if (p.getData() <root.getData())
return parent(root.getLeft(), p);
else if (p.getData() >root.getData())
return parent(root.getRight(), p);
else
return null;
}
22 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Deletion - Find Parent Node
CSBSTnode parent(BSTnode p) {
public
return parent(root, p);
} 20
private BSTnode parent(BSTnode root, BSTnode p) {
if4(root == null || root == p)
return null;
if (root.getLeft()==p || root.getRight()==p)
return root;
if (p.getData() <root.getData())
return parent(root.getLeft(), p); 59
else if (p.getData() >root.getData())
return parent(root.getRight(), p);
18 67
else
return null;
} 13 32 63 72
10 15 25 43
23 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Deletion – Leaf Node
CS public boolean isLeaf(BSTnode p) {
20 return (p.getLeft()==null &&
p.getRight()==null);
4 }
59
18 67
13 32 63 72
10 15 25 43
24 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Deletion – Has Left Child only
CS public Boolean hasOnlyLeftChild(BSTnode p) {
20 return (p.getLeft()!=null
&&p.getRight()==null);
4 }
59
18 67
13 32 63 72
10 15 25 43
25 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Deletion – Has Right Child only
CS public Boolean hasOnlyRightChild(BSTnode p) {
20 =null);
return (p.getLeft()==null &&p.getRight()!
4 }
59
18 67
13 32 63 72
10 15 25 43
26 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Deletion – Find Smallest Node
CS public BSTnode minNode(BSTnode root) {
20 if (root == null)
return null;
4 else if (root.getLeft() == null)
return root;
else
return
minNode(root.getLeft()) 59
}
18 67
13 32 63 72
10 15 25 43
27 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Deletion – Find Largest Node
CS public BSTnode maxNode(BSTnode root) {
20 if (root == null)
return null;
4 else if (root.getRight() == null)
return root;
else
return maxNode(root.getRight());
} 59
18 67
13 32 63 72
10 15 25 43
28 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
public void delete(int data) {
CP BST – Deletion
}
root = delete(root, data);
CS private BSTnode delete(BSTnode p, int data) {
BSTnode node2delete, newnode2delete;
20 BSTnode node2save, parent;
4 int saveValue;
node2delete = findNode(p, data);
if (node2delete == null)
return root;
parent = parent(p, node2delete);
if (isLeaf(node2delete)) {
if (parent == null)
return null;
if (data < parent.getData())
parent.setLeft(null);
else
parent.setRight(null);
return p;
29 Dr. Jonathan (Yahya) Cazalas
} Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
if (hasOnlyLeftChild(node2delete)) {
CP BST – Deletion
if (parent == null)
return node2delete.getLeft();
CS if (data <parent.getData())
20 parent.setLeft(parent.getLeft().getLeft());
4 else
parent.setRight(parent.getRight().getLeft());
return p;
}
if (hasOnlyRightChild(node2delete)) {
if (parent == null)
return node2delete.getRight();
if (data <parent.getData())
parent.setLeft(parent.getLeft().getRight());
else
30 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
parent.setRight(parent.getRight().getRight());
Data Structures - I
“No Bonus” marks for this course anymore
CP BST – Deletion
CS
newnode2delete = minNode(node2delete.getRight());
20 saveValue = newnode2delete.getData();
4 p = delete(p, saveValue);
node2delete.setData(saveValue);
return p;
}
31 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP
CS
20
4
Binary Search Tree
Practice Problems
32 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Binary Tree – Sum the Nodes
CS
20
4 public int sumNodes(intBSTnode p) {
if (p == null)
return(0);
else
return p.data + sumNodes(p.left) + sumNodes(p.right);
}
33 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Binary Tree – Count the Nodes
CS
20
4 public int countNodes(intBSTnode p) {
if (p == null)
return(0);
else
return 1 + countNodes(p.left) + countNodes(p.right);
}
34 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Binary Tree – Count the Leaf Nodes
CS
20
public int numLeaves(intBSTnode p) {
4 if (p != NULL) {
if (p.left == NULL && p.right == NULL)
return 1;
else
return numLeaves(p.left) + numLeaves(p.right);
}
return 0;
}
35 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Binary Tree – Print Even Values
CS
20 public void printEven(intBSTnode p) {
4 if (p != null) {
if (p.data % 2 == 0)
System.out.print(p.data + “ ”);
printEven(p.left);
printEven(p.right);
}
}
36 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Binary Tree – Print Odd Values
CS
20 public void printOdd(intBSTnode p) {
4 if (p != null) {
printOdd(p.left);
if (p.data % 2 == 1)
System.out.print(p.data + “ ”);
printOdd(p.right);
}
}
37 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Binary Tree – Compute Height
CS public int height(intBSTnode root) {
int leftHeight, rightHeight;
20 if ( root != null ){
4 if (root.left == null && root.right == null)
return 0;
leftHeight = height(root.left);
rightHeight = height(root.right);
if (leftHeight > rightHeight)
return leftHeight + 1;
else
return rightHeight + 1;
}
return -1;
}
38 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Binary Tree – Largest in BST
CS
20 public intBSTnode largest(intBSTnode B) {
4 if (B == null)
return null;
else if (B.right == null)
return B;
else
return largest(B.right);
}
39 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Binary Tree – Nodes with One Child
CS public int one(intBSTnode p) {
if (p != NULL) {
20 if (p.left == null){
4 if (p.right != null)
return 1 + one(p.right);
else
return 0;
}
else if (p.right == null)
return 1 + one(p.left);
else
return one(p.left) +
one(p.right);
}
40 } Jonathan (Yahya) Cazalas
Dr. Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP
CS
20
4
Allah (Alone) is Sufficient for us, and He is
the Best Disposer of affairs (for us).(Quran 3 :
173)
41 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
