Convert a binary tree to threaded binary trees

“We know the important property of binary tree. Each level has 2^n nodes. If that is the case, what is the number of empty nodes in the leaves. empty nodes mean left or right null near the tree leaves. If its a perfectly balanced tree, you get around 2^<height of the tree> nodes. Which is huge!! and goes for a big waste!!”

See first

http://analgorithmaday.blogspot.com/2011/06/applications-of-traversals.html

Introduction

   This is another memory optimization concept where you need to reuse unused space present in the linked list and get easy traversal to parents. And remember the complex problem you would have heard about,

Converting a binary tree to a doubly linked list in-order way without using extra space & reusing the empty left& rights.

Problem Description: http://nirmalthacker.wordpress.com/2007/03/31/algorithm-problem-binary-tree-to-list/

This problem is simply nothing but making a binary tree a threaded binary tree with some extra linkages done for getting the doubly linked list property.

There is one more problem for more interested people,

http://www.careercup.com/question?id=3424767

Find the pre-order traversal of a tree without using recursion, stack, extra memory. You can reuse the space already present in the tree and create temporary nodes if required.

There are many applications & interview questions like this which requires prior & complete knowledge of threaded binary trees.

Concept

  How threading is done? We know that around 2^<height of the tree> nodes are empty. Which mostly constitutes 50% of the nodes in the tree. There is a mathematical proof for this.

 Let a null LEFT reference point to the predecessor in in order, and
  let a null RIGHT reference point to the successor in in order.

We need to use the concepts of in-order predecessor and successor to do this threading of trees. Please read through http://analgorithmaday.blogspot.com/2011/06/applications-of-traversals.html carefully.

Code

We will see the code in next section. There are two types of threaded binary tree,

• Single threaded with only in-order successors connected
• Double threaded with both in-order successors and predecessors connected