Data Structures and Algorithms part 2

Andy Novocin

Daily Problem

Suppose you want to design a dictionary class, D, using a stack class, S, as your underlying structure. (Perhaps you are working in a restricted environment.)

You may assume S.push(pointer), S.pop(), and S.isEmpty() in \( \mathcal{O}(1) \) time, you may make \( \mathcal{O}(1) \) stacks, and you need not worry about overflow.

What would be the asymptotic worst-case complexity of your D.Search(key), D.Insert(pointer), D.Delete(pointer), D.Successor(pointer), D.Predecessor(pointer), D.Minimum(), and D.Maximum()?

Remember Sorted Linked Lists?

Really wanted to do Binary Search.

No access to medians.

Let's try anyway.

Point HEAD to median, point PREV and NEXT to sub-medians

You've created a Binary Search Tree!

Graph Theory Tree

Tree: Undirected graph in which any two vertices are connected by one (and only one) simple path.

(No cycles!)

Computer Science Version

Technically our 'trees' will be directed and rooted.

A directed graph with special vertex, root, so that there is a unique directed path from the root to any other vertex.

Binary Tree

Binary Tree: A tree data structure in which each node has \( \leq 2 \) children, one left, one right.

Recursively, A Binary Tree is either empty or a triple (L, N, R) where L, R are binary trees and N is a node / data set.

Binary Search Tree

A Binary Tree with sortable nodes and the magic property:

All nodes in the left subtree have smaller value than the nodes in the right subtree.

The left and right subtrees contain smaller and larger (resp) values than the root node.

Binary vs Binary Search

They can be unbalanced!

Define the Class

This code on IDEONE

template<class T>
class Tree {
    T data;
    Tree* left;
    Tree* right;
    Tree* parent;


template <class T>
Tree<T>* Tree<T>::search(string fname){
  if ( == fname){
    return this;
  if ( < fname){
    if (right == NULL){
      return right;
    return right->search(fname);
  if ( > fname){
    if (left == NULL){
      return left;
    return left->search(fname);

A New Challenge(r) Appears

Challenge Problem 1:

Suppose 1 to 1000 are nodes in a binary search tree. We are searching for 363.

Which of the following sequences can NOT be our path?

Challenge Problem 2:

Professor Bunyan proposes the following property of BSTs:

Suppose that the search for \( k \) ends in a leaf.

Consider three sets

\( A \), the keys to the left of the search path,

\( B \), the keys on the search path,

and \( C \), the keys to the right of the search path.

He claims that any \( a \in A, b \in B, c \in C \) must satisfy \( a \leq b \leq c \).

Give the smallest possible counter example to the professor's claim.

Min (Max)

template <class T>
Tree<T>* Tree<T>::max(){
  if (right == NULL){
    return this;
  return right->max();

Insert (standard)

template <class T>
void Tree<T>::insert(T node_data, Tree * t_parent){
  if ( <{
    if (right == NULL){
      right = new Tree<T> (node_data);
      right->parent = this;
    right->insert(node_data, this);
  if (left == NULL){
    left = new Tree<T> (node_data);
    left->parent = this;
  left->insert(node_data, this);

Insertion Order Matters!


template <class T>
Tree<T>* Tree<T>::traverse(){
  if (left != NULL){
  cout << "Data: " << << " : " << data.phone_number << endl;
  if (right != NULL){

In-Order Traversal

Successor (Predecessor)

template <class T>
Tree<T>* Tree<T>::successor(){
  if (right != NULL){
    return right->min();
  Tree<T>* up_one = parent;
  Tree<T>* proxy = this;
  while ((up_one != NULL) and (proxy == up_one->right)){
    proxy = up_one;
    up_one = up_one->parent;
  return up_one;

Who is next?

Delete (Not coded here)

Requires Transplanting within the Tree

Draw Picture On Board