Crisp Reading Notes on Latest Technology Trends and Basics

Overview

Background

In memory-constrained architectures, it may be necessary to work without a lot of memory. In these cases, we try to execute iterative algorithms instead of recursive algorithms.

Problem Description

To develop an Iterative algorithm to do Post-order traversal of a Binary Tree.

  • Note :- The additional storage should not be proportional to the depth of the tree.
  • In the first cut, an extra Parent pointer may be assumed

Incidentally, this is also an “Amazon Interview Question”

The Algorithm

First Node

The first node in a Post-Order traversal is derived as follows

  1. Start from the Root
  2. If a node has a left child, traverse the left link
  3. Otherwise if the node has a right link, traverse the right link.
  4. Keep repeating this till you hit a leaf
Node *first_child( Node *root ) {

Node *curr = root;

while (1) {

if( curr->left != NULL ) {

curr = curr->left;

continue;

}

if( curr->right != NULL ) {

curr = curr->right;

continue;

}

return curr;

}

}

First Child of SubTree

The above fragment of code can be used for any subtree node (not just the Root)

Next Child

Given an arbitrary node, to find the next child, there are two cases

  1. If the current node is a right sibling of its parent,
  • Both left and right subtrees of the parent have been e xamined.
  • So, next node is the parent
  1. If the current node is a left sibling of its parent
  • The right subtree has not yet been examined, and must be examined before the parent.
  • So the next node is the first post-order child of the right subtree (if it exists)

The code is therefore as follows

Node *next_child( Node *curr ) {

// If node is the right child of the parent

if ( curr->parent->right == curr ) {

return parent;

}

// If node is the left child of the parent

if ( curr->parent->left == curr ) {

if ( curr->parent->right == NULL ) {

return curr;

}

else {

return first_child( curr->parent );

}

}

}

Putting it all together

The root is the last node traversed in a post-order traversal.

The traversal is supposed to end when the child returned is the root node

// Routine to traverse all nodes of the tree

void traverse_all( Node *root ) {

Node *curr = first_child(root);

visit(curr);

while( curr != root ) {

curr = next_child(curr);

visit(curr);

}

}

Further Ideas

Incidentally, the use of the “parent” pointer is extra memory, that should well be avoided.

Unfortunately, to avoid the stack, this was deemed necessary.

We need to look at other possibilities, such as the “Threaded Pointer”, and temporary tree rotation to see if these possibilities will work.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Tag Cloud

%d bloggers like this: