• Trees are structures that represent hierarchical data.
  • They are formed of nodes connected together in parent-child relationships.
  • There is a special node, called the root, which has no parent.
  • Each child node may have its own children.


Example of a tree of colors broken into a hierarchy.


  • Root:
    • The foor tis first node in the tree. In the above diagram 'Colors' is the root node.
  • Internal / Branch node:
    • Any node which has children is called an internal or 'branch' node.
  • Leaf:
    • Any node which doesn't have children.
    • The plural of leaf is 'leafs'.
  • Child & Parent:
    • Any node that has child nodes becomes the parent to those nodes.
    • Leaf nodes are never parents.
    • In the above diagram, 'Blue' is a parent while 'Dark Blue' and 'Light Blue' are its children.
  • Siblings:
    • If two children have the same parent then they are siblings.
  • Descendant & Ancestor:
    • The descendant / ancestor relationship is similar to that of child and parent, except that the descendant doesn't need to be an immediate child of the ancestor.
    • 'Dark Blue' is a descendant of 'Colors'.
  • Breadth:
    • The number of leaf nodes.
  • Height:
    • The height of a tree is the length of the longest path between the root node and a leaf node.
    • In the example above, this would be 2.
  • Size:
    • The total number of nodes in the tree.
  • Degree:
    • The degree of a node is the number of children it has.
    • Leaf nodes have a degree of 0.
    • The degree of a tree is the largest degree of any of its nodes.
      • In the above image, the degree of the tree is 3.
  • Level:
    • The distance from a node to the root.
      • The root is at level 0.
      • It's children are at level 1.
      • Their children are at level 2.
      • and so on.
    • The level can also be defined as a set of all nodes at the same level.
  • Forest:
    • An ordered set of trees.

Rooted vs unrooted trees

  • When we refer to a tree, we are referring to a rooted tree.
  • However unrooted, (aka free) trees also exist.
    • the only constraint on an unrooted tree is that there exists a single unique path between any two nodes.

Ordered vs unordered trees

Example of two trees that are ordered differently.
  • Ordered trees:
    • The children of an ordered tree have a specific order.
    • In the above image:
      • The trees are not considered equal.
      • This is because the children of the 'a' node are in different orders.
    • If a tree is ordered then we can refer to a specific child by its index, e.g. the first child of 'a'.
    • Ordered trees are the default. When someone refers to a 'tree' assume they are referring to an ordered tree.
  • Unordered (aka oriented) trees:
    • The children of an unordered tree do not have a specific order.
    • In the above image:
      • The trees are considered equal.
      • The order of the children is not important when determining equality.
    • It is not possible to refer to a child by index.

K-ary trees

  • A k-ary tree (aka m-ary tree) is a tree in which each node has at most 'k' children.
  • A binary tree is a k-ary tree with k = 2. Each node has at most two children: Example of a binary tree.
  • A ternary tree is a k-ary tree with k=3.
  • K-ary trees differ are not proper trees:
    • K-ary trees can be completely empty, while trees must have at least one node.
    • K-ary trees can have empty nodes:
      • In the image above, the 'b' node has no left child. I.e. its first child is empty.

Code (Python)

# -*- coding: utf-8 -*-
class Node:
    def __init__(self, data):
        self.children = [] = data

    def addNode(self, node):
        node = node if isinstance(node, Node) else Node(node)
        node.parent = self
        return self # returns self so addNode() can be chained    

    def __str__(self, path = '', last = True):
        ret = path + ('' if not path else ('└─ ' if last else '├─ ')) + + '\n'
        for child in self.children:
            ret += child.__str__(path + ('   ' if last else '│  '), child == self.children[-1])
        return ret
tree = \
    Node("Colors") \
            .addNode('Light Blue')
            .addNode("Dark Blue")) \
            .addNode("Light Red")
            .addNode("Dark Red")) \
            .addNode("Light Green")
            .addNode("Dark Green"))

  ├─ Blue
  │  ├─ Light Blue
  │  └─ Dark Blue
  ├─ Red
  │  ├─ Light Red
  │  └─ Dark Red
  └─ Green
     ├─ Light Green
     └─ Dark Green

Time Complexity

  • Trees are often more efficient than simpler data structures such as arrays and lists.
  • if an operation takes linear time on a list (such as searching) then it will usually take logarithmic time on a tree.
    • Assuming the tree is well organized.