Trees in Data Structures: Binary Trees and Binary Search Trees

What is a tree?

A tree is a way to store data that has a top-down shape. Each item sits in a node. Nodes are joined by edges.

• Root: the single top node. It has no parent.
• Parent and child: a node directly above is the parent; nodes directly below are its children.
• Siblings: children of the same parent.
• Leaf: a node with no children. Internal node: a node with at least one child.
• Subtree: any node together with everything below it.

A tree has no loops, and there is exactly one path between any two nodes. With n nodes it always has n − 1 edges.

Levels, depth, height and degree

Depth of a node = number of edges from the root to it. The root has depth 0. All nodes at the same depth form a level.

Height of a tree = the largest depth of any leaf. A tree with only a root has height 0. (Some books count nodes instead of edges, so they add 1. Always check which rule is used.)

Degree of a node = number of children it has.

Storing a rooted tree: the parent array

Number the nodes 1 to n. For each node, write its parent; write 0 for the root. Example: nodes 1..5 with parent array [0, 1, 1, 2, 2] means 1 is the root, 2 and 3 are children of 1, and 4 and 5 are children of 2. Leaves are nodes that never appear in the array as a parent (here 3, 4, 5). Another way is a child list: for each node, list its children.

Binary trees

A binary tree is a tree where each node has at most two children, called the left child and the right child.

• Full binary tree: every node has 0 or 2 children.
• Complete binary tree: all levels are full except maybe the last, which is filled from the left.
• Perfect binary tree: all levels completely full. A perfect tree of height h has 2^h+1 − 1 nodes.

Level k of a binary tree can hold at most 2^k nodes. In code, a node is usually a record with key, left and right (links that are empty/None when there is no child).

Binary search trees (BST)

A BST is a binary tree with one rule at every node: all keys in the left subtree are smaller, all keys in the right subtree are bigger.

Search

Start at the root. If the key equals the node, stop. If it is smaller, go left; if bigger, go right. If you reach an empty link, the key is not there.

Insert

Search for the key; where the search falls off the tree, attach a new leaf.

In a balanced BST with n nodes, search takes about log₂ n steps (1,000,000 keys → about 20 checks). If keys are inserted already sorted (10, 20, 30, …) the BST becomes a long chain and search becomes slow (n steps).

Tree traversals

A traversal visits every node exactly once.

• Pre-order: root, then left subtree, then right subtree. Good for copying a tree.
• In-order: left, root, right. On a BST this prints keys in sorted order.
• Post-order: left, right, root. Good for deleting a tree or working out folder sizes.
• Level-order (breadth-first): level by level, left to right, using a queue.

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.key)
    inorder(node.right)

Try it at home

Write the numbers 50, 30, 70, 20, 40, 60, 80 on seven slips of paper. Place them on the floor one at a time using the BST rule. Then pick up the slips in in-order and check they come out sorted. Now try inserting 10, 20, 30, 40: what shape do you get?

Key formulas and definitions

• Edges in a tree = nodes − 1
• Max nodes at level k of a binary tree = 2^k
• Max nodes in a binary tree of height h = 2^(h+1) − 1
• Balanced BST search ≈ log₂ n steps
• Pre-order: Root-Left-Right; In-order: Left-Root-Right; Post-order: Left-Right-Root

Worked examples

Common mistakes

• Counting height in nodes in one place and edges in another. Fix one rule (here: edges) and stick to it.
• Thinking a BST only compares a node with its parent. The rule applies to the whole left and right subtree.
• Mixing pre-order and post-order. Remember where the root (parent) goes: PRE = first, POST = last.
• Believing a BST is always fast. Sorted input makes a chain, and search becomes as slow as a list.