CS211: Binary Trees
Table of Contents
Introduction
If you went to kindergarten/grade school in the United States there's a good chance you had to complete a school project where you sketched out a family tree. The top of the tree would consist of distant, or not so distant, ancestors and it would eventually pass through your parents and end up at you. Each person's name in the tree would have two branches going up, representing parents1, but could have many branches going down, representing children. If we prune the nodes that are not strictly ancestral by only keeping parents and no siblings, what you drew was a binary tree and it is one of the most used, fundamental data structures in computing.
What is a Binary Tree?
A binary tree is a data structure which, like linked lists, must satisfy a handful of logical constraints:
- All binary trees must have a starting node called the root node
- All nodes in the tree can have at most two children.
- All nodes may have at most one parent.
Any tree-like structure which breaks these rules are by-definition not binary trees. For example, the Linux filesystem can easily be represented as a tree, but it is not a binary tree because a single directory (node) may have more than two files (children).
Binary Tree Terminology
The root node is the starting node in a tree ("root" for the roots, or anchoring point, of a tree). Nodes can connect to other nodes. Nodes that are connected to a given node that go up the tree are called parents. Nodes that are connected to a given node that go down the tree are called children. Nodes that have no children are called leaves. The height of a tree indicates how many jumps from the root need to be made to reach the farthest leaf. The following diagram visualizes this terminology:
+-------+
| root | ← root (height = 0)
+-------+
/ \
/ \
+-------+ +-------+
| A | | B | ← children of root
+-------+ +-------+ (root is their parent)
/ \ \
/ \ \
+-------+ +-------+ +-------+
| C | | D | | E | ← children of A and B
+-------+ +-------+ +-------+
\
\
+-------+
| F | ← leaf (no children)
+-------+
C and D are also leaves.
Height of tree = 3 (root → B → E → F)
We call a binary tree full if every node has either two children or none. We call a binary tree complete if every level is filled with nodes, except the last level where nodes do not have to be filled in completely, but must be packed to the left. Finally, we call a binary tree perfect if all interior nodes have two children and all leaves have the same depth or same level. We can visualize the different types of trees below:
Full
+-------+
| |
+-------+
/ \
+-------+ +-------+
| | | |
+-------+ +-------+
/ \
+-------+ +-------+
| | | |
+-------+ +-------+
every node has 0 or 2 children
Complete
+-------+
| |
+-------+
/ \
+-------+ +-------+
| | | |
+-------+ +-------+
/ \ /
+-------+ +-------+ +-------+
| | | | | |
+-------+ +-------+ +-------+
last level not fully filled but packed left
Perfect
+-------+
| |
+-------+
/ \
+-------+ +-------+
| | | |
+-------+ +-------+
/ \ / \
+-------+ +-------+ +-------+ +-------+
| | | | | | | |
+-------+ +-------+ +-------+ +-------+
all leaves at same depth, all internal nodes have 2 children
Binary Tree Traversal
There are three standard ways of traversing a Binary Tree: preorder, inorder, and postorder. I'll outline the pseudocode for preorder:
1: preorder(node): 2: print(node.data) # Perform computation 3: preorder(node.left) 4: preorder(node.right)
Here, we have a recursive function which looks at a node in a binary tree, performs a computation, and then moves to the left node, recursively, and then the right node. We can see it visually below:
+-------+
| 1 | ← visit first (root)
+-------+
/ \
+-------+ +-------+
| 2 | | 5 | ← visit 2 before 5
+-------+ +-------+
/ \ / \
+-------+ +-------+ +-------+ +-------+
| 3 | | 4 | | 6 | | 7 |
+-------+ +-------+ +-------+ +-------+
Order visited: 1 → 2 → 3 → 4 → 5 → 6 → 7
Rule: visit the current node BEFORE visiting children
always go left before right
Steps:
visit 1 (root)
go left → visit 2
go left → visit 3 (leaf, go back up)
go right → visit 4 (leaf, go back up)
go right → visit 5
go left → visit 6 (leaf, go back up)
go right → visit 7 (leaf)
I'll leave it as an exerise to the reader to try out inorder traversal (where the computation is between moving left and right) and postorder traversal (where the computation is after moving left and right).
Binary Search Tree
Binary trees in and of themselves are often not useful in the real world. They become more interesting when further constraints are added to them. One such binary tree variant is the binary search tree. Binary search trees are binary trees with one additional wrinkle: they maintain a strict order of nodes. For any given node, all values in its left subtree must be less than that node's value, and all values in its right subtree must be greater. Here is an example of a binary search tree:
+-------+
| 8 |
+-------+
/ \
+-------+ +-------+
| 3 | | 12 |
+-------+ +-------+
/ \ / \
+-------+ +-------+ +-------+ +-------+
| 1 | | 5 | | 10 | | 15 |
+-------+ +-------+ +-------+ +-------+
It can be seen that for every node, all of the values to the right of it are greater than its value, and all of the values to the left are smaller.
Binary Search Algorithm
If you've ever tried looking through the index of a book to find a specific word, you've likely already employed the basic logic of binary search. Let's say you're in a C textbook and you're trying to find the word function. First, you open up the index to the A's and grab a hunk of pages and flip right to left. Next, you find yourself in the T's, which you know comes after F, so you grab a hunk of pages and flip left to right. Now, you're in the D's which you know comes before F, so you grab a hunk of pages and flip right to left again. Finally, we've made it to the F's and function should be smack dab in the middle of the page.
This more or less describes the algorithm for performing a binary search on a binary search tree. The following pseudocode implements it more formally:
1: search(node, elem): 2: if node.data = elem: 3: return true 4: else: 5: if elem > node.data: 6: return search(node.right, elem) 7: else: 8: return search(node.left, elem)
We can visualize the binary search below:
+-------+
| 50 |
+-------+
/ \
+-------+ +-------+
| 25 | | 75 |
+-------+ +-------+
/ \ / \
+-------+ +-------+ +-------+ +-------+
| 12 | | 37 | | 62 | | 87 |
+-------+ +-------+ +-------+ +-------+
/ \ / \
+-------+ +-------+ +-------+ +-------+
| 6 | | 18 | | 81 | | 93 |
+-------+ +-------+ +-------+ +-------+
Searching for 81:
step 1: visit 50 candidates: whole tree (15 nodes)
81 > 50 → go right, left subtree eliminated
+-------+
| 50 |
+-------+
\
+-------+
| 75 |
+-------+
/ \
+-------+ +-------+
| 62 | | 87 |
+-------+ +-------+
/ \
+-------+ +-------+
| 81 | | 93 |
+-------+ +-------+
step 2: visit 75 candidates: 7 nodes
81 > 75 → go right, left subtree (62) eliminated
+-------+
| 75 |
+-------+
\
+-------+
| 87 |
+-------+
/ \
+-------+ +-------+
| 81 | | 93 |
+-------+ +-------+
step 3: visit 87 candidates: 3 nodes
81 < 87 → go left, right subtree (93) eliminated
+-------+
| 87 |
+-------+
/
+-------+
| 81 |
+-------+
step 4: visit 81 ✓ candidates: 1 node
found!
What you'll notice is that every single time a decision is made to move left or right half of the binary tree is ignored further down the search. The order of the binary search is what allows for this to occur. Intuitively, the smaller the portion of the tree we have to search, the faster the search will be. It turns out that binary search in a "well-balanced" binary search tree should take only about log₂(n) steps where n is the number of nodes in the tree. If we take n to be 15, corresponding to the number of nodes in the above tree, we'll find that log₂(15) ≈ 4 which is equivalent to the number of steps taken to get the search results!
Not all binary search trees are guaranteed to be "well-balanced", i.e. an even distribution of nodes across all levels.
Binary Search Tree API
We can define a BST API as follows:
init- Initializes a BST
insert- Inserts an element into the BST
search- Searches for an element in the BST
remove- Removes the desired element in the BST
is_empty- Indicates whether the BST is empty or not
free- Frees the BST
Inserting Elements into a Binary Search Tree
Binary search trees only work if their constraints are maintained. We can guarantee that elements are slotted into their proper place by utilizing the same traversal algorithm as the binary search (we'll assume here that elements must be unique):
1: insert(node, elem): 2: if node.data = elem: 3: ERROR 4: else: 5: if elem > node.data: 6: if node.right = null: 7: node.right ← elem 8: else: 9: insert(node.right, elem) 10: else: 11: if node.left = null: 12: node.left ← elem 13: else: 14: insert(node.left, elem)
We can visualize this algorithm by adding 70 to the previous BST:
+-------+
| 50 |
+-------+
/ \
+-------+ +-------+
| 25 | | 75 |
+-------+ +-------+
/ \ / \
+-------+ +-------+ +-------+ +-------+
| 12 | | 37 | | 62 | | 87 |
+-------+ +-------+ +-------+ +-------+
/ \ / \
+-------+ +-------+ +-------+ +-------+
| 6 | | 18 | | 81 | | 93 |
+-------+ +-------+ +-------+ +-------+
Inserting 70:
step 1: visit 50
70 > 50 → go right
step 2: visit 75
70 < 75 → go left
step 3: visit 62
70 > 62 → go right
right child is NULL → insert here!
+-------+
| 50 |
+-------+
/ \
+-------+ +-------+
| 25 | | 75 |
+-------+ +-------+
/ \ / \
+-------+ +-------+ +-------+ +-------+
| 12 | | 37 | | 62 | | 87 |
+-------+ +-------+ +-------+ +-------+
/ \ \ / \
+-------+ +-------+ +-------+ +-------+ +-------+
| 6 | | 18 | | 70 | | 81 | | 93 |
+-------+ +-------+ +-------+ +-------+ +-------+
Deleting Elements from a Binary Search Tree
Removing elements from a BST presents a greater challenge. For example, consider the tree in Listing 2. If we want to delete 81, then the process is trivial. But what if we want to delete 50? How could that be accomplished? If we naively replace it with 75 then something must be done about 62 and 87. This is why BST's will have a well-defined method for finding a successor node. A common solution is to find the smallest node that is greater than the node being removed. For example, if 50 is marked for deletion, then 62 will be chosen:
1: successor(n): 2: if n.right not = null: 3: return minimum(n.right) 4: s ← n.parent 5: while s not = null and n = s.right: 6: n ← s 7: s ← s.parent 8: return s
where minimum spans the leftmost children. This will always grab either the smallest element greater than n from its right subtree, or the lowest ancestor for which n lies in the left subtree—both of which are the next largest value in the tree relative to n.
We can then define deletion as follows:
1: delete(n): 2: if n.left = null or n.right = null: # Find a node without two children 3: y ← n # and set it equal to y 4: else: 5: y ← successor(n) 6: if y.left not = null: # x is set to the left or right child 7: x ← y.left # or nill if neither exist 8: else: 9: x ← y.right 10: if x not = null: # We then splice out y 11: x.parent ← y.parent 12: if y.parent = null: 13: tree.root ← x 14: else if y = y.parent.left: 15: y.parent.left ← x 16: else: 17: y.parent.right ← x 18: if y not = n: # If the succesor of n was spliced out 19: n.data = y.data # swap the data and return y for removal 20: return y 21:
We can see the algorithm in action with the above BST:
Deleting 50 (root, has two children):
Original:
+-------+
| 50 |
+-------+
/ \
+-------+ +-------+
| 25 | | 75 |
+-------+ +-------+
/ \ / \
+-------+ +-------+ +-------+ +-------+
| 12 | | 37 | | 62 | | 87 |
+-------+ +-------+ +-------+ +-------+
\
+-------+
| 70 |
+-------+
step 1: 50 has two children so find successor(50)
minimum of right subtree → 62
step 2: 62 has a right child (70)
x = 70
splice out 62, replacing it with 70
+-------+
| 50 |
+-------+
/ \
+-------+ +-------+
| 25 | | 75 |
+-------+ +-------+
/ \ / \
+-------+ +-------+ +-------+ +-------+
| 12 | | 37 | | 70 | | 87 |
+-------+ +-------+ +-------+ +-------+
step 3: copy 62 into node 50
+-------+
| 62 |
+-------+
/ \
+-------+ +-------+
| 25 | | 75 |
+-------+ +-------+
/ \ / \
+-------+ +-------+ +-------+ +-------+
| 12 | | 37 | | 70 | | 87 |
+-------+ +-------+ +-------+ +-------+
We can see that after the deletion the assumptions about the binary search tree are maintained.
Binary Seach Tree: Pros & Cons
Pros:
- Fastest possible search if balanced
- Dynamic size
- Naturally recursive structure
Cons:
- Loses search speed if unbalanced
- Memory overhead (storing pointers and data)
- No constant time operations
Exercises
- Implement a BST node as a
structin C. It should contain an integer data field, aleftpointer, arightpointer, and aparentpointer. Then implementinitwhich initializes an empty BST with arootpointer set toNULL. - Implement
insertfrom the pseudocode in the lecture in C. Test it by inserting the values(50, 25, 75, 12, 37, 62, 87)in that order and verifying the resulting tree matches the diagram shown in the lecture. - Implement
searchfrom the pseudocode in the lecture in C. Test it on the tree built in exercise 2 by searching for both values that exist and values that do not. What is the maximum number of nodes visited when searching a tree of height 3? - The lecture leaves inorder and postorder traversal as an exercise. Write the pseudocode for both and then implement all three traversals (preorder, inorder, postorder) in C. Run inorder traversal on the BST from exercise 2 and observe the output. What do you notice about the order of the values printed?
- Write a recursive function
heightin C that computes the height of a binary tree. Recall from the lecture that height is defined as the number of jumps from the root needed to reach the farthest leaf. Test it on the BST from exercise 2 and verify the result matches what you would expect from inspecting the tree diagram. Then test it on a tree with only a root node — what should the height be in that case? - The lecture notes that a BST "loses search speed if unbalanced." Starting from an empty BST, insert the values
(1, 2, 3, 4, 5, 6, 7)in that order. Draw the resulting tree. What does it look like? Use yourheightfunction from exercise 5 to measure its height and compare it to a balanced BST containing the same values. What does this tell you about the importance of insertion order? - Implement
deletefrom Listing 3 in C. Handle all three cases: deleting a leaf, deleting a node with one child, and deleting a node with two children. Test each case on the tree from exercise 2 and verify the BST property is maintained after each deletion. - Implement
successorfrom the pseudocode in the lecture in C. Test it by finding the successor of every node in the tree from exercise 2 and verify each result by inspection of the tree diagram. - Implement
freefor your BST. It should recursively free every node in the tree. Consider which traversal order is most appropriate for freeing nodes safely — preorder, inorder, or postorder — and explain your choice. Run your full BST implementation undervalgrindto confirm there are no memory leaks. - A perfect binary tree of height h contains 2^(h+1) - 1 nodes. Verify this formula for heights 1, 2, and 3 by drawing the trees and counting nodes. Then write a function
is_perfectthat returns 1 if a binary tree is perfect and 0 otherwise, using yourheightfunction from exercise 5 to help.
Footnotes:
This, of course, implies a purely geneological/biological family tree. Those with step parents might break that assumption. Similarly, descendents of the Hapsburgs may also quickly run into serious trouble.