Binary Trees..

What is a Binary Tree?


A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree.

What are the types of Binary Tree?

• A rooted binary tree is a tree with a root node in which every node has at most two sons.
• A full binary tree (sometimes proper binary tree or 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two sons.
• A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level. 
• A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
• A balanced binary tree is commonly defined as a binary tree in which the height of the two subtrees of every node never differ by more than 1.
• A Strictly Binary tree is a tree in which every non-leaf node in a binary tree has nonempty left and right subtrees.

Find the number of nodes given the height(depth) in a perfect Binary Tree?


Formula : n = 2^{h + 1} − 1 where h is the height of the tree.


Find the number of nodes given the height(depth) in a complete Binary Tree?


Formula : minimum nodes,n = 2^h
               maximum nodes,n = 2^{h + 1} − 1.


Find the depth of the tree if the tree is balanced?


Formula : d=log₂(n).


Operations to traverse a nonempty binary tree in preorder.


1) Visit the root.
2) Traverse the left subtree.
3) Traverse the right subtree.

Operations to traverse a nonempty binary tree in inorder.

1) Traverse the left subtree.

2) Visit the root.

3) Traverse the right subtree.

Operations to traverse a nonempty binary tree in postorder.

1) Traverse the left subtree.

2) Traverse the right subtree.

3) Visit the root.