Binary Trees Problems..............................................................
Pre-Order Traversal. Solutions...
In-Order Traversal. Solution...
Post-Order Traversal. Solution...
Finding Nth element in a Linked List. Solution...
Binary search method. Solution...
Generate mirror image tree of given tree. Solution...

The traversal of a binary tree is to visit each node in the tree exactly once. Binary tree traversal is useful in many applications. The order in which nodes of a linear list are visited is clearly from first to last. However, there is no such natural linear order for the nodes of a tree. The methods differ primarily in the order in which they visit the nodes. There are three popular methods of binary tree traversal. These methods are known as inorder traversal, preorder traversal and postorder traversal. In each of these methods nothing need be done to traverse an empty binary tree. The functions used to traverse a tree using these methods can be kept quite short if we understand the recursive nature of the binary tree. Recall that a binary tree is recursive in that each subtree is really a binary tree itself. Thus traversing a binary tree involves visiting the root node and traversing its left and right subtrees. The only difference among the methods is the order in which these three operations are performed.

To traverse a nonempty binary tree in preorder , we perform the following three operations:

  1. Visit the root.

  2. Traverse the left subtree in preorder.

  3. Traverse the right subtree in preorder.

To traverse a nonempty binary tree in inorder (or symmetric order):

  1. Traverse the left subtree in inorder.

  2. Visit the root.

  3. Traverse the right subtree in inorder.

To traverse a nonempty binary tree in postorder :

  1. Traverse the left subtree in postorder.

  2. Traverse the right subtree in postorder.

  3. Visit the root.

Many algorithms that use binary trees proceed in two phases. The first phase builds a binary tree, and the second traverses the tree. As an example of such an algorithm, consider the following sorting method. Given a list of numbers in an input file, we wish to print them in ascending order. As we read the numbers, they can be inserted into a binary tree such as the one of Figure 6. When a number is compared with the contents of a node in the tree, a left branch is taken if the number is smaller than the contents of the node and a right branch if it is greater or equal to the contents of the node. Thus if the input list is

20 17 6 8 10 20 7 18 13 12 5 6

The binary tree of Figure 6 is produced.



Figure 6

Such a binary tree has the property that all elements in the left subtree of a node n are less than the contents of n, and all elements in the right subtree of n are greater than or equal to the contents of n. A binary tree that has this property is called a Binary Search tree. If a binary search tree is traversed in inorder (left, root, right) and the contents of each node are printed as the node is visited, the numbers are printed in ascending order. Convince yourself that this is the case for the binary search tree of Figure 6. The program to implement this algorithm is given below

/* Program to implement a binary tree */

#include"alloc.h"

struct btreenode

{

struct btreenode *leftchild ;

int data ;

struct btreenode *rightchild ;

} ;

main( )

{

struct btreenode *bt ;

int req, i = 1, num ;

bt = NULL ; /* empty tree */

clrscr( ) ;

printf ( "Specify the number of data items to be inserted: " ) ;

scanf ( "%d", &req ) ;

while ( i++ <= req )

{

printf ( "Enter the data :" ) ;

scanf ( "%d", &num ) ;

insert (&bt, num ) ;

}

clrscr( ) ;

printf ( "\nInorder Traversal:" ) ;

inorder ( bt ) ;

printf ( "\nPreorder Traversal:" ) ;

preorder ( bt ) ;

printf ( "\nPostorder Traversal: " ) ;

postorder ( bt ) ;

}

/* inserts a new node in a binary search tree */

insert ( struct btreenode **sr, int num )

{

if ( *sr == NULL )

{

*sr = malloc ( sizeof ( struct btreenode ) ) ;

( *sr ) -> leftchild = NULL ;

( *sr ) -> data =num ;

( *sr ) -> rightchild = NULL ;

return ;

}

else /* search the node to which new node will be attached */

{

/* if new data is less, traverse to left */

if ( num < ( *sr ) -> data )

insert ( &( ( *sr ) -> leftchild ), num ) ;

else

/* else traverse to right */

insert (&( ( *sr ) -> rightchild ), num ) ;

}

return ;

}

/*traverse a binary search tree in a LDR (Left-Data-Right) fashion */

inorder ( struct btreenode *sr )

{

if ( sr != NULL )

{

inorder ( sr -> leftchild ) ; /* print the data of the node whose leftchild is NULL or the path

has already been traversed */

printf ( "%d ", sr-> data ) ;

inorder ( sr -> rightchild ) ;

}

else

return ;

}

/* traverse a binary search tree in a DLR (Data-Left-right) fashion */

preorder ( struct btreenode *sr )

{

if ( sr != NULL )

{

/* print the data of a node */

printf ( "%d ", sr -> data ) ; /* traverse till leftchild is not NULL */

preorder ( sr -> leftchild ) ;

/* traverse till rightchild is not NULL */

preorder ( sr -> rightchild ) ;

}

else

return ;

}

/* traverse a binary search tree in LRD (Left-Right-Data) fashion */

postorder ( struct btreenode *sr )

{

if ( sr != NULL )

{

postorder ( sr -> leftchild ) ;

postorder ( sr -> rightchild ) ;

printf ( "%d ", sr -> data ) ;

}

else

return ;

}

Interview Puzzles
GDI+
Ado.Net Tutorial
Asp.Net Tutorial
Lectures videos
Winform Tutorial
C#.Net Tutorial
Programming Tips And Tricks
Visual C++ Tutorial
Ado.net Tutorial
ActiveX Controls Tutorial
ATL COM Tutorial
COM Tutorial
Managed C++The Buddha And His Dhamma
Bea WebLogic Interviews
TCL Programming FAQ's
Computer Science Notes
Discrete Mathematics notes
Database Management System(DBMS) Faqs
Professional Practices Faqs
Lotus Notes Faqs
Beautiful advertisements
Programming interview Questions and answers Blog List
Human Resource Tips
Tips for Windows XP Systems
Tips for Internet and Computer users
Tips for better e-mail etiquette
JavaScript Faq's
VB Script FAQ's
HTML Faq's
Perl Scripting FAQ's
Winrunner Faq'sLinux FAQ's
CCNA cisco Certification
Data WareHousing Interview
Microsoft SharePoint Interview
C++ Interview
Siebel Customer Relationship Management FAQ's
C Programming Language- Step by step learning
Unix FAQ'sSample Source Code for all languages
Various Technical and academic certifications

Source Code

Certifications

Misceleneous technical Faq's

VC++  Blog

Data structures Blog

.Net Blog

C#.Net Blog

VB.Net Blog

ASP.Net Blog

ADO.Net Blog

Winform Blog

WCF / WPF Blog

Job Openings

Operating Systems Faqs

Sybase Faq's

Download free e-books

All scripting Faq's

Oracle Faq's

All technical Faq's

Hasya-Vyang hindi kavite

HR, Car, Finance Faq's

Finance and Investment Faq's

All Freshers Resources

All Placement Papers

QA and testing Faq's

Sql Server Faq's

Mainframes Faq's

Java Faq's

Sap Faq's

Jokes & Fun


Click here to enter your page's footer (optional).