Binary Search Trees

What's the deal with BST?

Node definition

Node:
  Left
  Right
  Parent

In Order Tree Walk

In Order Tree Walk:
  IOTW Left
  Print
  IOTW Right

Finding successor

You want to find the successor! The next value in the tree!

Tree Successor:
  if x.right != None:
    return Tree-Minimum(x.right)
  y = x.p
  While y != None and x == y.right
    x = y
    y = y.p
  return y

If the right value isn't empty, then you just want the min of the right value

          5
      3         7
   2    4    6     9

Successor of 5: 6 Successor of 3: 4

Else, you want to find it, Y is the lowest ancestor of x who's left child is also an ancestor of x. What the heck does that mean?

It means... go up and left until you can go right and then you're okay.