Lets discuss binary tree concepts and few basic frequently asked programming questions related to it.

**Binary tree** is tree in which each node can have **at the most two children**. This means each node can have 0 children (leaf node) , 1 children or two children. Generally referred as left child and right child. In terms, both left sub-tree and right sub-tree are also binary trees.

**Complete Binary tree:** A binary tree in which all the levels are complete filled except last level which is filled from left to right.

**Balanced Binary tree: **A binary tree in which difference between the height of left sub-tree and right sub-tree is 0 or 1

**Perfect or Full Binary tree:** A binary tree in which each node have exactly 0 or 2 nodes.

A complete binary tree and a perfect binary tree is always going to be balanced binary tree.

**Height of Binary tree: **

Lets consider ‘n’ total number of nodes in balanced binary tree and ‘l_{k}‘ is the numbers nodes at level ‘l’.

So, for k = 0 -> l_{0} = 1 (root node)

for k = 1 -> l_{1} = 2 (second level)

for k = 2 -> l_{2} = 4 (second level) and so on..

This means each node will have twice number of nodes from its previous level. Total number of nodes can be represent using this concept as:

2^{0 }+ 2^{1} + 2^{2 }^{ }+2^{3 }+2^{4 }+……+ 2^{h }= n here h is a height of tree

So, **2 ^{h+1 } -1 = n **(for understanding, 2

^{0+1}-1 -> 2

^{1}– 1 =1 for level 0 and so on..for each level we can compute)

Now, we will calculate hight of balanced binary tree if has n nodes using above expression:

2^{h+1 }= n+1

h+1 = lg(n+1)

h= lg(n+1) – 1

By l’Hopital’s rule this expression follows as: lg(n+1) – 1 = lg(n)

So, **h = lg(n)**

**In binary tree, a minimum height of tree for ‘n’ nodes can be |_lg(n)_| (ceiling function) and maximum height can be (n-1).**

**A perfect binary tree of height h has 2 ^{h }leaf nodes in terms of height and has (n+1)/2 leaf nodes in terms of ‘n’.**

**Tree Traversal:**

Traversal means visiting each node of a tree. Linear data structure like array, we traverse it in one direction starting from 0 index to last index of array. However, tree can be traversed in different ways.

**Level Order Traversal: **This is also known as breadth first traversal. Every node on a level before going to a lower level.

**Depth First Traversal: ** This traversal can be done in three ways, In-order, Pre-order and Post-order.

**Inorder traversal: <left><root><right>**

1. Traverse left sub tree.

2. Print data in root.

3. Traverse right sub tree.

Inorder traversal is used in binary search tree we get numbers sorted in sorted ascending order.

**Preorder traversal: <root><left><right>**

1. Print data in root.

2. Traverse left sub tree.

3. Traverse right sub tree.

By using preorder traversal we can make a copy of a tree.

**Postorder traversal: <left><right><root>**

1. Traverse left sub tree.

2. Traverse right sub tree.

3. Print data in root.

Postorder traversal is used when we want to delete a tree as we visit parent node after visiting its children.

**Note: To remember traversals simple method is to remember position of root with respect to prefix of name of traversal.**

**Implementation of traversals:**

Inorder traversal:

1 2 3 4 5 6 7 8 9 10 11 |
void InOrderTraversal(Node rt) { if (rt == null) return; else { InOrderTraversal(rt.left); Console.Write(" " + rt.value); InOrderTraversal(rt.right); } } |

Preorder traversal:

1 2 3 4 5 6 7 8 9 10 11 |
void PreOrderTraversal(Node rt) { if (rt == null) return; else { Console.Write(" " + rt.value); PreOrderTraversal(rt.left); PreOrderTraversal(rt.right); } } |

Postorder traversal:

1 2 3 4 5 6 7 8 9 10 11 |
void PostOrderTraversal(Node rt) { if (rt == null) return; else { PostOrderTraversal(rt.left); PostOrderTraversal(rt.right); Console.Write(" " + rt.value); } } |

In each traversal every node of a tree is visited so time complexity for tree traversal in O(n).

You can find more coding questions and solutions here.

Lets discuss about binary search tree in next session..