TreeSet - Binary Search Tree

Instance Variables

boolean contains(root, o)

Base Cases:

• Node = null

  • False—No children, didn’t find value

• node.data = value

  • True—Childs value is the same

Recursive case:

• Value < node.data

  • Left subtree

• Value > node.data

  • Right subtree

root = add(root, value)

Base cases

• Node = null

  • Value isn’t already in list

  • Return new node in this spot

• node.data = value

  • Value already exists

  • Return existing node—for path

Recursive cases

• Value < node.data

  • Assignment statement—left subtree

  • return node—for unwinding

• Value > node.data

  • Assignment statement—right subtree

  • return node—for unwinding

void toArray(root, list)

Base case

• node = null

  • No children—return

Recursive cases

• In-order traversal

  • Left subtree

  • Process node data—list

  • Right subtree

root = remove(root, value)

Base cases

• node = null

  • Value not here—return

• node.data = value

  • 0 children—replace parent with null

  • 1 child—replace parent with child

  • 2 children—replace parent with predecessor

Recursive cases

• Value < node.data

  • Assignment statement—left subtree

  • return node—for unwinding

• Value > node.data

  • Assignment statement—right subtree

  • return node—for unwinding

predecessor(node)

• Default—left child

• Replace it with the furthest right child

Iterator inner class

• Constructor

  • Sets up stack—makes smallest node be on top—furthest left

• next()

  • Stores the smallest node—on top

  • Sets up stack to have smallest on top—right child followed by furthest left