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

Flow chart, What is tha flow chart of algorithm

What is tha flow chart of algorithm

Explain arrays, Arrays :- To execute a stack we need a variable called top,...

Arrays :- To execute a stack we need a variable called top, that holds the index of the top element of stack and an array to hold the part of the stack.

The complexity ladder, The complexity Ladder: T(n) = O(1). It is ca...

The complexity Ladder: T(n) = O(1). It is called constant growth. T(n) does not raise at all as a function of n, it is a constant. For illustration, array access has this c

String pattern matching, Document processing is quickly becoming one of the...

Document processing is quickly becoming one of the dominant functions of computers. Computers are utilized to edit, search & transport documents over the Internet, and to display d

Design a binary search tree, Binary Search Tree usage: Write a progra...

Binary Search Tree usage: Write a program to compare the time taken for a search in a skewed tree, a balanced tree, and a random tree. Speci cally, your program should do the

Explain space complexity, Explain Space Complexity Space Complexity :...

Explain Space Complexity Space Complexity :- The space complexity of an algorithm is the amount of memory it requires to run to completion. Some of the reasons to study space

Explain multidimensional array, Multidimensional array: Multidimensional a...

Multidimensional array: Multidimensional arrays can be defined as "arrays of arrays". For example, a bidimensional array can be imagined as a bidimensional table made of elements,

Structure of an avl tree, Given is the structure of an AVL tree: struct ...

Given is the structure of an AVL tree: struct avl { struct node *left; int info; int bf; struct node *right; }; 2) A multiway tree of n order is an ord

Sorting, Define Hashing. Store the following values in a hash table of tabl...

Define Hashing. Store the following values in a hash table of table size 11 using division method: 25, 42, 96, 101, 102, 162, and 197. In case of collision, use other hash functio

Which sorting methods sorting a list which is almost sorted, Which sorting ...

Which sorting methods would be most suitable for sorting a list which is almost sorted  Bubble Sorting method.

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