Tree

A Tree is a connected (there is a path between every vertices) and acyclic graph. If one edge is added to the tree, it will form a cycle and if one edge is removed from the tree, it will become disconnected.

A Tree has (only one) designated root node and has child nodes. A leaf node has no child.

In a binary tree, nodes have at most two children. A perfect binary tree of n levels has 2^k-1 nodes.

A complete binary tree is a tree where all nodes have 2 children except nodes at the last level on the far right of the tree.

There are 4 ways to traverse a binary tree:

• In-order: left node, root node, the then right node (the most common)
• Pre-order: the root, the left node, then the right node
• Post-order: the left node, the right node, then the root node
• Level-order: BFS traversal

Resources

https://www.youtube.com/watch?v=oSWTXtMglKE