Implementing a Binary Tree With Links
Chapter Fifty-Seven
Syllabus topic Module 2, "Trees: Implementation and Traversals"
Pages 174 to 176 of 411
In one line
A linked binary tree node holds a value and two addresses, left and right, and every operation on it is a three line recursion because the definition of a tree is itself recursive.
The node
Where a linked list node held one address, a binary tree node holds two.
| Part | Holds |
|---|---|
| left | the address of the left subtree, or null |
| data | the value |
| right | the address of the right subtree, or null |
A leaf has both null. A node with one child has one null, and which one it is matters, by chapter 54.
The whole tree is reached through a single variable holding the address of the root, exactly as a linked list was reached through its head.
Why every operation is three lines
The definition is: a tree is empty, or a root with a left subtree and a right subtree.
So every operation has the same shape:
if the tree is empty: return the answer for empty
otherwise: combine this node with the answer for the left subtree
and the answer for the right subtree
That is all. The four operations below differ only in what "combine" means.
| Operation | Empty gives | Combine |
|---|---|---|
| size | 0 | 1 + left + right |
| height | -1 | 1 + max(left, right) |
| sum of values | 0 | value + left + right |
| count leaves | 0 | 1 if a leaf, else left + right |
Built and run
class BNode:
"""A binary tree node: a value and two subtrees."""
__slots__ = ("data", "left", "right")
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def __repr__(self):
return "BNode(%r)" % (self.data,)
class BinaryTree:
def __init__(self, root=None):
self.root = root
def is_empty(self):
return self.root is None
def size(self):
return self._size(self.root)
def _size(self, node):
if node is None:
return 0
return 1 + self._size(node.left) + self._size(node.right)
def height(self):
return self._height(self.root)
def _height(self, node):
if node is None:
return -1
return 1 + max(self._height(node.left), self._height(node.right))
def leaves(self):
return self._leaves(self.root)
def _leaves(self, node):
if node is None:
return 0
if node.left is None and node.right is None:
return 1
return self._leaves(node.left) + self._leaves(node.right)
def total(self):
return self._total(self.root)
def _total(self, node):
if node is None:
return 0
return node.data + self._total(node.left) + self._total(node.right)
def mirror(self):
"""Swap every left and right. A standard examination question."""
self._mirror(self.root)
def _mirror(self, node):
if node is None:
return
node.left, node.right = node.right, node.left
self._mirror(node.left)
self._mirror(node.right)
def shape(self):
return self._shape(self.root)
def _shape(self, node):
if node is None:
return "."
if node.left is None and node.right is None:
return str(node.data)
return "%s(%s, %s)" % (node.data, self._shape(node.left),
self._shape(node.right))
# 10
# / .
# 5 20
# / . .
# 3 7 30
tree = BinaryTree(BNode(10,
BNode(5, BNode(3), BNode(7)),
BNode(20, None, BNode(30))))
print("shape :", tree.shape())
print("size :", tree.size())
print("height :", tree.height())
print("leaves :", tree.leaves())
print("total :", tree.total())
print()
print("property 4 (leaves = two-child nodes + 1): leaves =", tree.leaves())
print(" nodes with two children: 10 and 5, so 2, and 2 + 1 =", 2 + 1)
print()
tree.mirror()
print("mirrored:", tree.shape())
tree.mirror()
print("twice :", tree.shape(), "(mirroring twice restores the tree)")
print()
empty = BinaryTree()
print("empty tree: size", empty.size(), "height", empty.height(),
"leaves", empty.leaves(), "shape", empty.shape())Implementing a Binary Tree With Links
shape : 10(5(3, 7), 20(., 30))
size : 6
height : 2
leaves : 3
total : 75
property 4 (leaves = two-child nodes + 1): leaves = 3
nodes with two children: 10 and 5, so 2, and 2 + 1 = 3
mirrored: 10(20(30, .), 5(7, 3))
twice : 10(5(3, 7), 20(., 30)) (mirroring twice restores the tree)
empty tree: size 0 height -1 leaves 0 shape .Every method is three or four lines, and every one handles the empty tree in its first line. That is not a coincidence: the empty case is the base of the recursion, so it cannot be an afterthought.
Chapter 55's property 4 is confirmed on this tree: 3 leaves, 2 nodes with two children.
And mirror applied twice restores the original, which is a check worth having: an operation that is its own inverse can be tested without a second implementation to compare against.
The three things that go wrong
1. Forgetting the empty case. node.left on a null node is an error, and it happens at the bottom of every recursion, so a missing base case fails on every tree with any depth at all.
2. Returning 0 for the height of an empty tree. Then a single node tree has height 1 and property 2 of chapter 55 stops working. The convention is -1 and chapter 52 said why.
3. Recursing but not combining. Calling self._size(node.left) and ignoring the result is a mistake that compiles, runs, and returns a wrong number quietly.
The ADT, as built
| Operation | Cost |
|---|---|
is_empty() | O(1) |
size(), height(), leaves(), total() | O(n), every node visited once |
mirror() | O(n) |
| insert a child at a known node | O(1) |
Note that size and height are O(n) here. They can be made O(1) by storing them and maintaining them, which is chapter 18's habit, and the AVL tree of chapter 71 does exactly that with height because it needs it on every insertion.
Quick revision
- A linked binary tree node holds a value and two addresses, left and right; a leaf has both null.
- The whole tree is reached through one variable holding the root.
- Every operation has one shape: answer for empty, else combine this node with the answers for the two
Implementing a Binary Tree With Links
subtrees.
- size, height, leaves and total differ only in what "combine" means; each is three lines.
- The empty case is the base of the recursion, so it is the first line, never an afterthought.
- Height of an empty tree is -1, or chapter 55's property 2 breaks.
- size and height are O(n) unless stored; the AVL tree stores height because it needs it constantly.
- Mirroring twice restores the tree, which is a free self check.
Test yourself
1. What does a linked binary tree node hold? A value and two addresses, left and right, each either a subtree or null.
2. Give the shape every recursive operation on a binary tree takes. If the tree is empty, return the answer for empty; otherwise combine this node with the results for the left and right subtrees.
3. Write size and height as recursions, and give the empty answer for each. size: 0 if empty, else 1 + size(left) + size(right). height: -1 if empty, else 1 + max(height(left), height(right)).
4. Why must the height of an empty tree be -1? So that a single node tree has height 0, which keeps chapter 55's relation between height and the maximum number of nodes correct.
5. Name the three common errors in writing these recursions. Forgetting the empty base case; using 0 for the height of an empty tree; and making the recursive call without combining its result.
6. Why is mirroring a useful operation to test with? Because it is its own inverse: applying it twice must restore the original tree, so it can be checked without writing a second implementation to compare against.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.