**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)

## Post a Comment