Binary search tree pseudocode

/* TreeNotes.txt CIS 250 Dave Klick Pseudocode for a binary search tree class. */ class Tree<T>: // define what each node is class Node T data Node left, right Node(T val): set data to val passed in getData(): return data display(): display data compareTo(Node n): return comparison of data to n.data toString(): could be a variety of output formats // instance variables for tree Node root = null DUPS_ALLOWED = true Tree(): nothing needs to be done here Tree(boolean flag) DUPS_ALLOWED = flag // search routine T find(T val) Node cur = root while cur is not null compare val to cur.data <: cur = cur.left >: cur = cur.right =: return cur.data return null // not found // insert value into tree boolean insert(T val) Node parent, cur Node n = Node(val) if root is null then root = n // only item in tree otherwise cur = root loop forever parent = cur compare val to cur.data <: cur = cur.left if cur is null then parent.left = n and return true >: cur = cur.right if cur is null then parent.right = n and return true =: if duplicates allowed then cur = cur.right if cur is null then parent.right = n and return true otherwise return false return false // should never get here traverse(): if root isn't null then traverse(root) traverse(Node node) if node.left isn't null then traverse(node.left) display node if node.right isn't null then traverse(node.right) public boolean delete(T val) { Node current = root, parent = root leftChild = true // search for node to delete while current.data != val parent = current if val < current.data then current = current.left leftChild = true otherwise current = current.right leftChild = false // if value not found, return false if current is null then return false // if we got here, then // 1. current refers to node to be deleted // 2. parent refers to its parent // 3. leftChild indicates current:parent relation // check for delete with no children if current's left and right are both null then if current == root then root = null otherwise if leftChild then parent.left = null otherwise parent.right = null // check for delete with one child - left otherwise if current.right is null then if current == root then root = current.left otherwise if leftChild then parent.left = current.left otherwise parent.right = current.left // check for delete with one child - right otherwise if current.left is null then if current == root then root = current.right otherwise if leftChild then parent.left = current.right otherwise parent.right = current.right // must be delete with two children otherwise // get successor of node to be deleted Nodes delNode = successor = successorParent = current // succesor is in right subtree ... Node tmp = delNode.right // ... and then left as far as possible // (smallest element in right subtree) while tmp is not null successorParent = successor successor = tmp tmp = tmp.left // do this part only if successor isn't right // child of node to be deleted if successor != delNode.right then // attach successor's child to it's parent successorParent.left = successor.right // make right subtree successor's right child successor.right = delNode.right // make deleted node's parent point to successor if current is root then root = successor otherwise if leftChild then parent.left = successor otherwise parent.right = successor // make left subtree successor's left child successor.left = current.left return true;