Binary Search Tree Algorithms
Definition
In a binary search tree the left subtree of every node holds only smaller values and its right subtree holds only larger values. Searching, adding and removing all start at the root and follow one branch down.
pseudocode
function searchTree(root, target):
node = root
while node != null:
if target == node.data then
return true
elseif target < node.data then
node = node.left
else
node = node.right
end if
end while
return false
end function| Operation | Steps |
|---|---|
| Search | Start at the root and compare the target with the node. If they are equal the item is found; if the target is smaller follow the left pointer; if it is larger follow the right pointer. Repeat until the item is found or a null pointer is reached, which means it is not in the tree |
| Add an item | Search for the item's position in the same way until a null pointer is reached, then create the new node there as a leaf |
| Remove a leaf node | Search for the node, then set the pointer in its parent that leads to it to null |
Adding M, F, T, B, H, P, W, K in that order builds the tree below, which is used for both traversals.
text
M
/ \
F T
/ \ / \
B H P W
\
KDepth-First (Post-Order) Traversal
Definition
A depth-first traversal follows one branch as far down as it can before backtracking to the most recent node that still has a branch to follow. In a post-order traversal each node is output after both of its subtrees: left subtree, right subtree, then the node itself.
pseudocode
procedure postOrder(node):
if node != null then
postOrder(node.left)
postOrder(node.right)
print(node.data)
end if
end procedureWorked Example
Post-Order Traversal of the Tree
Order visited: B, K, H, F, P, W, T, M. The root is always last in a post-order traversal.
| Step | What happens | Output so far |
|---|---|---|
| 1 | From M go left to F, then left to B. B has no children, so output B | B |
| 2 | Backtrack to F and go right to H. H has no left child, so go right to K. K is a leaf, so output K | B, K |
| 3 | Both subtrees of H are done, so output H. Backtrack to F, whose subtrees are now done, and output F | B, K, H, F |
| 4 | Backtrack to M and go right to T, then left to P. Output P, backtrack to T, go right to W and output W | B, K, H, F, P, W |
| 5 | Both subtrees of T are done, so output T. Backtrack to M and output it last | B, K, H, F, P, W, T, M |
Each recursive call is placed on the call stack, and returning from a call is what takes the algorithm back to the parent node. This is why a depth-first traversal uses a stack.
Breadth-First Traversal
Definition
A breadth-first traversal visits the nodes level by level: the root first, then every node on the next level from left to right, and so on down the tree. It uses a queue to hold the nodes that are waiting to be visited.
pseudocode
procedure breadthFirst(root):
queue.enqueue(root)
while NOT queue.isEmpty():
node = queue.dequeue()
print(node.data)
if node.left != null then
queue.enqueue(node.left)
end if
if node.right != null then
queue.enqueue(node.right)
end if
end while
end procedureWorked Example
Breadth-First Traversal of the Tree
Order visited: M, F, T, B, H, P, W, K.
| Node removed from the queue and output | Children added to the queue | Queue afterwards (front first) |
|---|---|---|
| M | F, T | F, T |
| F | B, H | T, B, H |
| T | P, W | B, H, P, W |
| B | None | H, P, W |
| H | K | P, W, K |
| P | None | W, K |
| W | None | K |
| K | None | Empty |
Key Point
| Feature | Depth-first (post-order) | Breadth-first |
|---|---|---|
| Order | Left subtree, right subtree, then the node | Level by level, left to right |
| Data structure used | Stack (the call stack when written recursively) | Queue |
| Root is output | Last | First |
| Typical use | Deleting a tree or evaluating an expression tree, where the children must be dealt with before their parent | Finding the node nearest the root that meets a condition |