A binary tree is a special type of tree that has at most two nodes.
Implementation
template <typename T>
class Tree {
public:
private:
struct Node {
T data;
Node* left;
Node* right;
};
}Traversing Trees
Trees can be traversed in a variety of arbitrary ways but are most commonly traversed in the following distinct three methods.
inOrder
Example
void inOrder(Node* nd){
if (nd! nullptr){
inOrder(nd->leftchild);
visit(nd);
inOrder(nd->rightchild);
}
}If the tree ingested is a Binary Search Tree, this would visit nodes in growing order. This algorithm recurses until the left base case is reached, then collapses to the right, then upwards.
preOrder
Example
void inOrder(Node* nd){
if (nd! nullptr){
visit(nd);
inOrder(nd->leftchild);
inOrder(nd->rightchild);
}
}postOrder
Example
void inOrder(Node* nd){
if (nd! nullptr){
inOrder(nd->leftchild);
inOrder(nd->rightchild);
visit(nd);
}
}Similarly to preOrder, this algorithm recurses left until it hits the base case, but will collapse right first before collapsing upwards.
Complexity
The complexity of the above algorithms is all
Since for each call we visit another two nodes, and the tree is binary and visits once.
Types of Binary Trees
Full
A full binary tree is a tree where every node has either 0 or 2 nodes.
Complete
A complete binary tree is a tree where every level is full except for the last, which is packed left.
Perfect
A perfect binary tree is a tree where all nodes have two children, except for the leaf nodes which are all at the same level. It’s effectively a pyramid.
Balanced
Balanced binary trees are trees where the left and right subtree’s height differs at most by one. This account for all nodes, not just the root node of the tree.
Properties
Size
A binary tree of height n has at most:
nodes.
In a full binary tree of height n, the number of nodes is at least:
AVL Tree Height
the height of an AVL tree with n nodes is