Binary Trees
A binary tree is a tree with the order of 2. Meaning that a node is either a leaf or has left and/or right child.
By adding empty leaves we can make sure the binary tree is always filled which can make certain operations and algorithms easier. We add the empty leaves by first adding 2 empty leaves to all leaves which make the leaves to inner nodes. Then all inner nodes that only have one child receive an empty leaf.
Traversal orders
There are multiple ways to traverse a tree each one giving a different result.
Pre-order, NLR
In this order a node visited before its left and right subtree is traversed.
- Visit the current node.
- Recursively traverse the current node's left subtree.
- Recursively traverse the current node's right subtree.
Post-order, LRN
In this order a node is visited after its left and right subtree has been traversed.
- Recursively traverse the current node's left subtree.
- Recursively traverse the current node's right subtree.
- Visit the current node.
In-order, LNR
In this order a node is visited in between the traversal of its left and right subtree.
- Recursively traverse the current node's left subtree.
- Visit the current node.
- Recursively traverse the current node's right subtree.
