Constructing Binary Tree from given Preorder and Inorder Traversal.

Let us consider the following traversals:
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F


In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.


                                                                       A
                                                                       /\
                                                                      /  \
                                                            D B E    F C


We recursively follow above steps and get the following tree.

                                                                       
                                                                       A
                                                                       / \
                                                                      /   \
                                                                    B     C
                                                                    /\      /
                                                                   /  \    /
                                                                 D  E  F
Algorithm: buildTree()

1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex.
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.

Applet for Binary Tree Traversals.

Click the link below for interactive Binary Tree Traversal applet:

http://nova.umuc.edu/~jarc/idsv/lesson1.html

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.