CS 624
Lecture 7: Binary Search Trees
1 Graphs, paths, and trees
Definition A path in a graph is a sequence
v0 , v1 , v2 , · · · , vn
where each vj is a vertex in the graph and where for each i, vi and vi+1 are joined by an edge. (If
the graph is directed, then the edge must go from vi to vi+1 .)
To make things simple, we insist that any path contain at least one edge.
Usually we write
v 0 → v 1 → v 2 → · · · → vn
to denote a path. It is understood that the arrow represent edges.
A path in a graph is simple iff it contains no vertex more than once.
Definition A loop in a graph is a path which begins and ends at the same vertex.
A loop v0 → v1 → v2 → · · · → vk is simple iff
1. k ≥ 3 (that is, there are at least 4 vertices on the path), and
2. it contains no vertex more than once, except of course for the first and last vertices, which are
the same, and
3. That (first and last) vertex occurs exactly twice.
1.1 Exercise Prove that a simple loop contains no edge more than once.
Definition A tree is a connected1 undirected graph in which there are no simple loops.
1.2 Exercise Prove that if x and y are any two distinct vertices in a tree, there is a unique simple path
from x to y.
Hint: If there were two simple paths from x to y, then of course you could follow one forwards,
followed by the other one backwards to see that there is a loop in the graph. However, this loop
1 Do you know what it means to say that a graph is connected? If you don’t, you need to look it up right now.
1
, 2 2 TRAVERSING BINARY TREES
might not be a simple loop, which is what you would need to get a contradiction. However, if the
paths are not identical, then you should be able to take part of the first path followed by part of the
second (going backwards) to produce a simple loop in the graph. Be as precise as you can in doing
this. Give names to everything you are talking about. Remember that I can’t read your mind.
Definition A rooted tree is a tree with a distinguished vertex, which we call the root. We will
denote the root by r.
Definition If T is a rooted tree with root r, if x and y are vertices in T (and either or both of them
might be r) and if there is a simple path from r through x to y, then we say that x is an ancestor
of y and y is a descendant of x. If the part of the path from x to y consists of exactly one edge,
we say that x is the parent of y and y is a child of x.
Note that a vertex is both an ancestor and a descendant of itself. But a vertex cannot be its own
parent.
1.3 Exercise
1. Prove that a vertex in a rooted tree can have at most one parent.
2. Prove that every vertex other than the root has exactly one parent.
1.4 Exercise Prove that in a rooted tree T , if x is an ancestor of y and y is an ancestor of x, then
x = y.
1.5 Exercise Suppose T is a rooted tree with root r and x #= r is an vertex in T . (This is just a standard
way of saying that x is a vertex in T and x #= r.)
Further, suppose a and b are both ancestors of x. And to make things simple, suppose that a #= b.
Prove that either a is an ancestor of b or b is an ancestor of a.
1.6 Exercise Prove that any two nodes x and y in a rooted tree have a unique least common ancestor
z. This simply means that there is a path P1 from z to x, and a path P2 from z to y, and that the
only vertex those two paths have in common is z. (And further, that there is exactly one node z
with this property.)
We think of the root as being at the top of the tree, so the least common ancestor is the ancestor
that is as far away “down” the tree as possible. That’s where the term “least” comes from.
2 Traversing binary trees
When we write pseudocode involving binary trees, we will denote the left and right children of a
node x by x. left and x. right, respectively, and for brevity, we will denote the parent of x by x.p. If
x has no parent (which of course can only happen if x is the root) then by convention we say that
x.p = nil.
There are three basic ways to traverse (or “walk”) a binary tree. The idea is that we want to perform
some function at each node. This is called “visiting” the node. And we want to recursively traverse
each child of the node. The only difference between these three methods of traversal is the order in
which these things happen.
Lecture 7: Binary Search Trees
1 Graphs, paths, and trees
Definition A path in a graph is a sequence
v0 , v1 , v2 , · · · , vn
where each vj is a vertex in the graph and where for each i, vi and vi+1 are joined by an edge. (If
the graph is directed, then the edge must go from vi to vi+1 .)
To make things simple, we insist that any path contain at least one edge.
Usually we write
v 0 → v 1 → v 2 → · · · → vn
to denote a path. It is understood that the arrow represent edges.
A path in a graph is simple iff it contains no vertex more than once.
Definition A loop in a graph is a path which begins and ends at the same vertex.
A loop v0 → v1 → v2 → · · · → vk is simple iff
1. k ≥ 3 (that is, there are at least 4 vertices on the path), and
2. it contains no vertex more than once, except of course for the first and last vertices, which are
the same, and
3. That (first and last) vertex occurs exactly twice.
1.1 Exercise Prove that a simple loop contains no edge more than once.
Definition A tree is a connected1 undirected graph in which there are no simple loops.
1.2 Exercise Prove that if x and y are any two distinct vertices in a tree, there is a unique simple path
from x to y.
Hint: If there were two simple paths from x to y, then of course you could follow one forwards,
followed by the other one backwards to see that there is a loop in the graph. However, this loop
1 Do you know what it means to say that a graph is connected? If you don’t, you need to look it up right now.
1
, 2 2 TRAVERSING BINARY TREES
might not be a simple loop, which is what you would need to get a contradiction. However, if the
paths are not identical, then you should be able to take part of the first path followed by part of the
second (going backwards) to produce a simple loop in the graph. Be as precise as you can in doing
this. Give names to everything you are talking about. Remember that I can’t read your mind.
Definition A rooted tree is a tree with a distinguished vertex, which we call the root. We will
denote the root by r.
Definition If T is a rooted tree with root r, if x and y are vertices in T (and either or both of them
might be r) and if there is a simple path from r through x to y, then we say that x is an ancestor
of y and y is a descendant of x. If the part of the path from x to y consists of exactly one edge,
we say that x is the parent of y and y is a child of x.
Note that a vertex is both an ancestor and a descendant of itself. But a vertex cannot be its own
parent.
1.3 Exercise
1. Prove that a vertex in a rooted tree can have at most one parent.
2. Prove that every vertex other than the root has exactly one parent.
1.4 Exercise Prove that in a rooted tree T , if x is an ancestor of y and y is an ancestor of x, then
x = y.
1.5 Exercise Suppose T is a rooted tree with root r and x #= r is an vertex in T . (This is just a standard
way of saying that x is a vertex in T and x #= r.)
Further, suppose a and b are both ancestors of x. And to make things simple, suppose that a #= b.
Prove that either a is an ancestor of b or b is an ancestor of a.
1.6 Exercise Prove that any two nodes x and y in a rooted tree have a unique least common ancestor
z. This simply means that there is a path P1 from z to x, and a path P2 from z to y, and that the
only vertex those two paths have in common is z. (And further, that there is exactly one node z
with this property.)
We think of the root as being at the top of the tree, so the least common ancestor is the ancestor
that is as far away “down” the tree as possible. That’s where the term “least” comes from.
2 Traversing binary trees
When we write pseudocode involving binary trees, we will denote the left and right children of a
node x by x. left and x. right, respectively, and for brevity, we will denote the parent of x by x.p. If
x has no parent (which of course can only happen if x is the root) then by convention we say that
x.p = nil.
There are three basic ways to traverse (or “walk”) a binary tree. The idea is that we want to perform
some function at each node. This is called “visiting” the node. And we want to recursively traverse
each child of the node. The only difference between these three methods of traversal is the order in
which these things happen.
