Trees

Trees#

A Tree is a data structure.

The Tree is a data structure particularly good at representing hierarchical relationships. Unlike linear data structures such as linked lists, trees model a parent-child structure. Common examples include family trees, organizational charts, filesystem directories, and the chapter structure of a book. They, and other tree-based logic, are very, very common. In other words, it’ll be important to not only understand how trees (the data structure) work, but also to get used to thinking in a tree-like way.

Flowchart Example

Just like how all linked list nodes are (eventually) accessible from a single head node, a tree’s elements, also stored in nodes, are eventually accessible from a single top-most node, known as the root.

Terminology#

To discuss trees, we use the following standard terminology:

  • Node: An element within the tree.

  • Root: The single node at the top of the tree, which has no parent.

  • Parent: For two nodes A and B, A is the parent of B if A is directly above B in the hierarchy and connected to it. Each node has at most one parent.

  • Child: The inverse of a parent. If A is the parent of B, then B is the child of A.

  • Sibling: Two nodes are siblings if they share the same parent.

  • Ancestor: A node’s parent, its parent’s parent, and so on, up to the root.

  • Descendant: A node’s children, its children’s children, and so on.

  • External Node (or Leaf): A node with no children.

  • Internal Node: A node with one or more children.

  • Subtree: A portion of a tree consisting of a node and all of its descendants. This portion is itself a valid tree!

Binary Trees#

A very common example of a tree is the binary tree. As you might guess, a binary tree has up to two children for each parent. A binary tree built to hold data might start being implemented like this:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

Here’s a picture of such a tree:

The height of a tree is the length of the path of the node furthest from the root. The height of this tree is 3, because no node is more than three links away from the root.

Trees have heights, but nodes have depths. This is the number of links between the node and the root.

Let us think about how short a binary tree can be in order to store \(n\) nodes. If \(n=1\), the tree has height 0. If \(N\) is 2 or 3, the tree can be of height

  1. A tree can have up to \(n=7\), and still only be height 2. This table continues that thought process:

Height

Maximum \(n\)

0

1

1

3

2

7

3

15

4

31

5

63

Note that \(n\) is essentially doubling each time we add another depth. This demonstrates the main advantage of a Tree: while a Linked List takes \(O(n)\) time to get from the head to an arbitrary node, in a sufficiently densely filled Tree, no node is more than \(O(\log(n))\) away from the root.