Notes

Trees

Daniel Weibel
Created 1 Sep 2017
Last updated 9 Nov 2017

First of All…

A tree is just a special type of graph, namely a connected acyclic graph.

Terminology

Tree Terminology

Height of a Node

  • Number of edges on the longest path from this node to a leaf
  • Leaves have height 0

Height of a Tree

  • Height of the root

Depth of a Node

  • Number of edges on the path from this node to the root
  • Root has depth 0

Levels of a Tree

  • A tree has Height + 1 levels
  • Root is at level 1

Binary Trees

TODO: draw example binary tree with e.g. 10 nodes

  • Height of a binary tree with $n$ nodes: $\lfloor\Log n\rfloor$
  • Maximum number of nodes in a binary tree with $n$ levels: $2^n-1$

Binary Search Trees (BST)

Binary Heaps