1 Binary Search Trees CMSC 132 Department of Computer Science University of Maryland, College Park 2 Overview Binary Search Tree Search Properties Construction Insertion Deletion Polymorphic BST Polymorphic, recursive linked list 3 Binary Search Tree (BST) Key property Value at node Smaller values in left subtree Larger values in right subtree Example X > Y X < Z Y X Z 4 Binary Search Trees Examples Binary search trees Non-binary search tree 5 10 30 2 25 45 5 10 45 2 25 30 5 10 30 2 25 45 5 Iterative Search of BST Node Find( Node n, Value key) { while (n != null) { if (n.data == key) // Found it return n; if (n.data > key) // In left subtree n = n.left; else // In right subtree n = n.right; } return null; } Find( root, keyValue ); 6 Recursive Search of Binary Tree Node Find( Node n, Value key) { if (n == null) // Not found return( n ); else if (n.data == key) // Found it return( n ); else if (n.data > key) // In left subtree return Fin...