Trees

Tree :

--------------------------------------------------------------------------------------------------------------------------------------------------
root: node with no parents
edge: refers to link from parent to child node
leaf: node with no children
siblings: children of same parents
size of a node: number of descendants it has including itself
level: set of all nodes at a given depth. (root node has level 0)
depth: length of path from root to the node (tree with only one node has depth 0)
height: length of the path from that node to the deepest node (tree with only one node has height 0)
skew tree: if every node in tree has only one child (types: right skew tree, left skew tree)
--------------------------------------------------------------------------------------------------------------------------------------------------

Binary Tree:

Types:
--------------------------------------------------------------------------------------------------------------------------------------------------
strict binary tree: each node has exactly two children
full binary tree: if each node has exactly two children and all leaf nodes are at same level
complete binary tree: if height of a tree is h then all leaf nodes are at height h or h-1
--------------------------------------------------------------------------------------------------------------------------------------------------
Properties:
--------------------------------------------------------------------------------------------------------------------------------------------------
number of nodes in a full binary tree is 2^h+1-1
number of leaf nodes in a full binary tree 2^h
number of nodes in a complete binary tree is between 2^h to 2^h+1-1
number of null pointers in a complete binary tree of n nodes is n+1
number of binary trees possible with n nodes is 2ⁿ-n
--------------------------------------------------------------------------------------------------------------------------------------------------