Trees

#programming #data-structures

The general data-structure of tree is trivial, therefore I am not including most of it here.
Majority of the stuff included here are definitions or specific terminology which can be difficult to remember.

Basic property of trees is that there are no cycles.

• The degree of a node is defined as the number of children it has.
• A node with degree $0$ is considered a leaf node. All other nodes, including root, are considered internal nodes.
• The height of a tree is defined as the maximum depth of any node, with the height of just root being $0$.
  • The height of empty tree is $-1$
• A full binary tree in which each node has either 2 children or none.
• A complete binary tree in which all levels are completely filled, except possibly the last. The last is filled in left-to-right manner.

Traversals

• Preorder : Itself before children
• Postorder : Children before itself.
• Inorder : Left, itself, right.