Tree: Non-Linear Data Structure in which data is organized in a hierarchical manner.  It is very fast for information retrieval and searching operations. 

Important Terminology of a Binary Tree.

Node: Each element in a tree is called a node.

Edges: Lines connecting two nodes, it is also known as branches. 

Parent Node: The immediate predecessor of a node (node that comes just before a node).

Child Node: The immediate successors of a node (node that comes just next in line).

Root Node: The node that doesn't have any parent node.

Leaf Node: The node that doesn't have any child node. The node other than the leaf node is known as a non-leaf or terminal node. 

Level: Distance of that node from the root.

Height: Total number of level, depth of the tree, Level+1=Height

Siblings: All nodes having the same parent. All siblings are at the same level but it is not necessary that nodes at the same level are siblings.

Path: It is a way to reach a node from any other node. In a tree, there is only one path possible between any two nodes. Path length = Number of Edges on the path.

Degree: The number of children or subtrees connected to a node.

Forest: The subtrees we get after removing the root of the main tree is collectively called as Forest (also known as a set of disjoint trees).  

Strictly Binary Tree: Each node in the tree is either a leaf node or has exactly two children. There is no node with one child. 

Extended Binary tree: Each Empty subtree is replaced by a special node then the resulting tree is extended binary tree or 2-tree.

Full Binary tree: All the levels have the maximum number of nodes.

**If the number of any node is k, then the number of the left child is 2k, the number of right children is 2k+1, and the number of its parent is k/2.

Complete Binary Tree: All the levels have the maximum number of nodes except possibly the last node.

Important Properties of a Binary Tree.

P1. The maximum number of nodes possible on any level i is 2^i where i>=0.

P2. The maximum number of nodes possible in a binary tree of height h is 2^h-1.

P3. The minimum number of nodes possible in a binary tree of height h is equal to h. A tree with a minimum number of nodes is called skew trees.

P4. If a binary tree contains n nodes, then its maximum height possible is n and the minimum height possible is log2(n+1).

P5. In a non-empty binary tree, if n is the total number of nodes and e is the total number of edges, then e = n-1.

P6. In a non-empty binary tree, if n is the number of nodes with no child and m is the number of nodes with 2 children, then n = m+1.

Traversal in Binary Tree

1. Breadth-First Traversal (Level Order Traversal)

2. Depth First Traversal

A. Preorder Traversal (Root, Left, Right)

B. Inorder Traversal (Left, Root, Right)

C. Postorder Traversal (Left, Right, Root)