Binary Search Trees Overview Recursive linked list ops Binary Trees 2 Recursion w LL Recursion can be used to traverse a linked list Any recursive solution has an iterative counterpart recursive is sometime more elegant though 2 functions countNodes ListNode showReverse ListNode 3 Counting Nodes in a List int NumberList numNodes return countNodes head Must provide public member function Recursive function must start at head but head can t be passed in from outside the class int NumberList countNodes ListNode nodePtr if nodePtr NULL return 1 countNodes nodePtr next else return 0 4 Head Counting Nodes in a List 3 4 5 3000 3008 3016 Null int NumberList countNodes ListNode nodePtr if nodePtr NULL return 1 countNodes nodePtr next else return 0 5 Head Counting Nodes in a List 3 4 5 3000 3008 3016 int NumberList countNodes 3000 if nodePtr NULL return 1 countNodes 3008 else return 0 Null st ac k 6 Head Counting Nodes in a List 3 4 5 3000 3008 3016 int NumberList countNodes 3000 int NumberList countNodes 3008 if nodePtr NULL 1 countNodes 3008 return else if nodePtr NULL 1 countNodes 3016 returnreturn 0 else return 0 Null st ac k 7 Head Counting Nodes in a List 3 4 5 3000 3008 3016 int NumberList countNodes 3000 int NumberList countNodes 3008 if nodePtr NULL 1 countNodes 3008 return NULL else if nodePtr int NumberList countNodes 3016 1 countNodes 3016 returnreturn 0 else if nodePtr NULL return 0 1 countNodes NULL return else return 0 Null st ac k 8 Head Counting Nodes in a List 3 4 5 3000 3008 3016 int NumberList countNodes 3000 int NumberList countNodes 3008 if nodePtr NULL 1 countNodes 3008 return NULL else if nodePtr int NumberList countNodes 3016 1 countNodes 3016 returnreturn 0 int NumberList countNodes NULL else if nodePtr NULL return 0 1 countNodes NULL return elseif nodePtr NULL return return 0 1 countNodes nodePtr next else return 0 Null st ac k 9 Head Counting Nodes in a List 3 4 5 3000 3008 3016 int NumberList countNodes 3000 int NumberList countNodes 3008 if nodePtr NULL 1 countNodes 3008 return NULL else if nodePtr int NumberList countNodes 3016 1 countNodes 3016 returnreturn 0 else if nodePtr NULL return 0 1 0 return else return 0 Null st ac k 10 Head Counting Nodes in a List 3 4 5 3000 3008 3016 int NumberList countNodes 3000 int NumberList countNodes 3008 if nodePtr NULL 1 countNodes 3008 return else if nodePtr NULL 1 1 returnreturn 0 else return 0 Null st ac k 11 Head Counting Nodes in a List 3 4 5 3000 3008 3016 int NumberList countNodes 3000 if nodePtr NULL return 1 2 else return 0 finally returns 3 to numNodes Null st ac k 12 Displaying Nodes in Reverse Order int NumberList displayBackwards return showReverse head Must provide public member function Recursive function must start at head but head can t be passed in from outside the class int NumberList showReverse ListNode nodePtr if nodePtr NULL showReverse nodePtr next cout nodePtr value 13 Head Counting Nodes in a List 3 4 5 3000 3008 3016 void NumberList showReverse ListNode nodePtr if nodePtr NULL showReverse nodePtr next cout nodePtr value Null 14 Head Counting Nodes in a List 3 4 5 3000 3008 3016 void NumberList showReverse 3000 if nodePtr NULL showReverse 3008 cout nodePtr value Null 15 Head Counting Nodes in a List 3 4 5 3000 3008 3016 void NumberList showReverse 3000 void NumberList showReverse 3008 if nodePtr NULL if nodePtr NULL showReverse 3008 nodePtr value cout showReverse 3016 cout nodePtr value Null 16 Head Counting Nodes in a List 3 4 5 3000 3008 3016 void NumberList showReverse 3000 void NumberList showReverse 3008 if nodePtr NULL void NumberList showReverse 3016 if nodePtr NULL showReverse 3008 cout nodePtr value if nodePtr NULL showReverse 3016 nodePtr value cout showReverse NULL cout nodePtr value Null 17 Head Counting Nodes in a List 3 4 5 3000 3008 3016 void NumberList showReverse 3000 void NumberList showReverse 3008 if nodePtr NULL void NumberList showReverse 3016 if nodePtr NULL showReverse 3008 cout nodePtr value void NumberList showReverse NULL if nodePtr NULL showReverse 3016 nodePtr value cout if nodePtr NULL showReverse NULL cout nodePtr value showReverse NULL cout nodePtr value Null 18 Head Counting Nodes in a List 3 4 5 3000 3008 3016 void NumberList showReverse 3000 void NumberList showReverse 3008 if nodePtr NULL void NumberList showReverse 3016 if nodePtr NULL showReverse 3008 cout nodePtr value if nodePtr NULL showReverse 3016 nodePtr value cout showReverse NULL cout nodePtr value Null 19 Head Counting Nodes in a List 3 4 5 3000 3008 3016 void NumberList showReverse 3000 void NumberList showReverse 3008 if nodePtr NULL if nodePtr NULL showReverse 3008 nodePtr value cout showReverse 3016 cout nodePtr value Null 20 Head Counting Nodes in a List 3 4 5 3000 3008 3016 void NumberList showReverse 3000 if nodePtr NULL showReverse 3008 cout nodePtr value Null 21 Binary Trees 22 Binary Tree Binary Tree non linear linked structure each node may point to 2 other nodes every node has exactly 1 predecessor tree pointer 23 Binary Tree tree pointer p t f a null null null null z null null 24 Binary Tree Terminology tree pointer Root Node p t f a null null null Left Subtree null z null Leaf Node null 25 Binary Search Tree class interface ifndef INTBINARYTREE H define INTBINARYTREE H class IntBinaryTree private struct TreeNode int value TreeNode left TreeNode right TreeNode root void insert TreeNode TreeNode void destroySubTree TreeNode void deleteNode int TreeNode void makeDeletion TreeNode void displayInOrder TreeNode void displayPreOrder TreeNode void displayPostOrder TreeNode Binary Search Tree class interface public IntBinaryTree Constructor root NULL IntBinaryTree Destructor destroySubTree root void insertNode int bool searchNode int void remove int void showNodesInOrder displayInOrder root void showNodesPreOrder displayPreOrder root void showNodesPostOrder displayPostOrder root endif Inorder Traversal of a Binary Search Tree void IntBinaryTree displayInOrder TreeNode nodePtr if nodePtr displayInOrder nodePtr left cout nodePtr value endl displayInOrder nodePtr right Search for a specific value within a Binary Search Tree bool IntBinaryTree searchNode int num TreeNode nodePtr root while nodePtr if nodePtr value num return true else if num nodePtr value nodePtr nodePtr left else nodePtr nodePtr right return false Insert implementation insertNode creates a new node to hold num as its value and passes it to the insert function void IntBinaryTree insertNode int num TreeNode newNode Pointer to a new