Non-recursive implementation of preorder traversal, Data Structure & Algorithms

Assignment Help:

For preorder traversal, in the worst case, the stack will rise to size n/2, where n refer to number of nodes in the tree. Another method of traversing binary tree non-recursively that does not employ stack requires pointers to the parent node (called threaded binary tree).

A threaded binary tree is a binary tree wherein every node which does not have a right child has a THREAD (a third link) to its INORDER successor. By doing this threading we ignore the recursive method of traversing a tree and employ of stack, that makes use of many memory and time.

A node structure of threaded binary is following :

For a threaded binary tree the node structure varies a bit and its like this -

struct NODE *leftchild;

int node_value;

struct NODE *rightchild;

struct NODE *thread;  /* third pointer to its inorder successor */

}


Related Discussions:- Non-recursive implementation of preorder traversal

STACK, WHAT IS THE PURPOSE OF STACK IN C

WHAT IS THE PURPOSE OF STACK IN C

Entity relationship diagram, This question is based on the requirements of ...

This question is based on the requirements of a system to record band bookings at gigs. (A 'gig' is an event at which one or more bands are booked to play). You do not need to know

What are expression trees, What are expression trees?  The leaves of an...

What are expression trees?  The leaves of an expression tree are operands, like as constants or variable names, and the other nodes have operators. This certain tree happens to

Which data structure is used for implementing recursion, Which data structu...

Which data structure is used for implementing recursion Stack.

Program on radix sort., Write a program that uses the radix sort to sort 10...

Write a program that uses the radix sort to sort 1000 random digits. Print the data before and after the sort. Each sort bucket should be a linked list. At the end of the sort, the

#, if two relations R and S are joined, then the non matching tuples of bot...

if two relations R and S are joined, then the non matching tuples of both R and S are ignored in

Need it urgently, Write an assembly program to separate the number of posit...

Write an assembly program to separate the number of positive numbers and negative numbers from a given series of signed numbers.

Perform breadth -first search, You are given two jugs, a 4-gallon one and a...

You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring marker on it. There is a tap that can be used to fill the jugs with water. How can you get exac

Explain critical path and chain, 1.  Using the traditional method of CPM: ...

1.  Using the traditional method of CPM: a.  What activities are on the critical path? b.  What is the expected total lead time of the project? 2.  Using CCPM: a.  What

System defined data types, System defined data types:- These are data t...

System defined data types:- These are data types that have been defined by the compiler of any program. The C language contains 4 basic data types:- Int, float,  char and doubl

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd