[DSA] binary tree

terminology
the root: the beginning of a tree.

every node is possibly the root node for the nodes below it. eg. the parent node.

parent node, the n-1 lvl of the n's lvl node.
child node, the n+1 lvl of the n's lvl node.

(n-1)
|
___n____
| |
(n+1) (n+1)

edge, the path for traversal to happend.
leaves, the lowest lvl in the tree.

a binary tree, a tree where each parent node only have 2 children.

binary search tree (BST)

a binary tree, where the root node is always the middle value of the list of values.

remember binary search from previous week?
what are the 2 possible condition to be satisfied before one can qualify for binary search?

BST it self is not efficient. there is a possibility that the insertion of the node will cause it to behave like a worst case binary tree.

we need a sorted BST, where each time a node is inserted the tree is "sorted" to find out which is the new node. What are the implications if the tree are always sorted when insertion or deletion is done??? Is there any other possible way to enhance it?

3 ways for tree traversal
-Inorder
Traverse the left subtree
Visit the current parent
Traverse the right subtree

-Preorder
Visit the current parent
Traverse the left subtree
Traverse the right subtree

-Postorder
Traverse the left subtree
Traverse the right subtree
Visit the current parent


uses of binary tree data structure
- compression
- encoding
- conversion of mathematical formula to prefix or post fix form
- data structure of choice for "fast" retrieval of search items

there are many other type of binary tree
full binary tree
perfect binary tree
balanced binary tree
self balancing binary tree