Create a binary tree using an array

 

Introduction

  Its a reiterate of the same concept of mapping an array to a binary tree. We use this helper routine for creating binary trees used in our problems. So thought about showcasing the code to do that.

Solution

if you have an array like,

arr[] = { 2,3,6,1,8,2,3}

Total: 7 elements. To form a balanced binary tree out of the above array, we have to follow the below index to node mapping for the tree!!

root = i

left = 2i+1

right = 2i+2

(Assuming starting index of array is 0)

For creating the above balanced tree, you need to do a level order traversal.

We already have some examples (See references). But lets think simple way.

Algorithm:

- queue the first node

- loop

- de-queue from the vector, create a new node + left and right with data.

- push left & right of current node into the queue

- exit when array length is exceeded!!

struct BinTree

{

    int data;

    BinTree *left;

    BinTree *right;

    BinTree(int data) {

        this->data = data;

        this->left = NULL;

        this->right = NULL;

    }

};

BinTree* createBNode(int data)

{

    return new BinTree(data);

}

BinTree* arr_to_tree(int *arr, int size)

{

    BinTree *newTree, *root;

    vector<BinTree*> node_list;

    int i=0;

    root = createBNode(arr[0]);

    node_list.push_back(root);

    while(!node_list.empty())

    {

        newTree = node_list.front();

        node_list.erase(node_list.begin());

        if(2*i + 1 >= size)

            break;

        newTree->left = createBNode(arr[2*i+1]);

        node_list.push_back(newTree->left);

        if(2*i+2 >= size)

            break;

        newTree->right = createBNode(arr[2*i+2]);

        node_list.push_back(newTree->right);

        i+=1;

    }

    return root;

}

void main()

{

    BinTree *tree;

    int arr[] = { 2,3,4,6};

    tree = arr_to_tree(arr,4);

}

 

Reference

http://analgorithmaday.blogspot.in/2011/06/level-order-insert-in-binary-tree.html

Find power of 2

 

Introduction

  This something simple to understand recursion. Just for a time pass code recipe. :)

Concept

Recursion base condition: 

2⁰ = 1

Generic formula,

pow2(n) = { 1 , when n=0

                  2*pow2(n-1), when n>1

The above formula works out well to find the powers of 2.

Code

double pow2(double val)

{

  if(val == 0)

    return 1;

  return 2*pow2(val-1);

}

void main()

{

    cout<<pow2(1000);

}

Warning

• This is not an alternate to pow function. The runtime implements it using for loop.

Thinking in recursive way–Mathematics

“I simply forget recursion and always use debuggers to understand it. Debuggers are hated by mathematical programmers. Why you need debuggers btw when you use math to prove your program will work for all corner cases ?”

Introduction

   The funny thing about mathematics and programming is that, if you pick one, you will drop another. A perfect example of chicken and egg problem. But programs written for critical applications always goes for mathematical analysis.

  To understand Recursion, you need to know some mathematical functions which already aptly follow recursion.

Lets see the factorial function which is defined with below,

Lets see an example, where n=4

4! = 4 x 3!
4! = 4 x 3 x 2!
4! = 4 x 3 x 2 x 1!
4! = 4 x 3 x 2 x 1 x 1

Concept

   Ok. Factorial is basic. We all knew about all the mathematical functions and their direct mapping with recursion.

  Now, where to use recursion? just for mathematical functions? This is the question of programmers, not the mathematicians. :)

  I hope you read the previous post on Loop invariant. That is the basis for deciding whether to go for recursion or not. :)

  Let’s say, you need to maintain multiple values constant, logged for future processing in a loop. You usually would go for using stacks or some data structure to keep a log of all data required in future. 

Example:

   count the number of nodes in a tree

   How to think about this problem loud out? usually people mug up things. :) But that’s not the right way.

A simple logic, start with 0 nodes in a tree, means tree variable is NULL.

This is base condition. Then, what we need to do, we need count of left tree and right tree.

The code goes like below, so simple,

if(tree == NULL)

  return 0;

return count(tree->left) + 1 + count(tree->right);

Mathematical representation:

count(t) =   0, when t=0

                  1, when t=1

                 count(t->left) + count(t->right), when t > 1

Let’s try for 3,

count(3 node tree) = count(1) + count(left + right node)

              = 1 + count(1 left node) + count(1 right node) = 3

Analysis

  Here, the loop invariant is at any time, we have the node’s visited on hand. that is, if we have visited all tree->left, we start visiting tree->right. Once we are done with all tree->right, we reach base condition for every node. If the node count is 1, then its 1. :)

 This is what works out simply for anything that uses recursion, quick sort, merge sort.. any algorithm we see, the base condition value is the important one. After you design the base condition in the form of mathematical function, writing recursive program is simpler.

Thinking in recursive way–Loop Invariant

“Even though, we can solve problems using recursion. It is tough to think something in a recursive way without the knowledge of functional programming”

See also

http://analgorithmaday.blogspot.in/2011/02/loop-invariant-to-prove-correctness.html
http://analgorithmaday.blogspot.com/2011/01/recursionfibonacci-series.html
Introduction
  Thinking in recursive way is little bit tough. But if you have programmed with a functional language then, there is no other way to think. :) When even loops are designed with recursion, you cover all the corner cases isn’t it? That’s the reason why robotics uses functional programming languages as it’s pure magic, fun and well defined mathematical entity rather than the program we write day-to-day.
  But why recursion is taught to be tough when it is so simple to implement and code looks so neat? The real application of recursion can only be seen in functional languages like Erlang.
Concept
  From what we have learnt about loop invariant, what is an invariant? variable is used to vary data, when does invariant used?
  In dummies way, invariant is nothing but a stack!! The data will never vary but get logged somewhere and get popped when needed. So, the data once set never changes but get logged.
In a for loop, we have looping variable which will be set once and the operation done for a single loop is constant!!.. The operation can only be the same for the next iteration without affecting what we are up to. otherwise, what we are doing in the loop is of no use. Simply this is called Loop invariant. When recursion is nothing but loops, understanding loops will give an intro to recursion. But Loops are simpler versions of recursion where usually people never think about constant inside the loop.
Example:

//Example of useless for loop with no loop invariant

for(int i=0; i<10;i++);

//Example of storing the values

// loop invariant: at any time a[i-1] will have data upto i-1

int a[20];

for(int i=0;i < 10; i++) { a[i] = i; }

In the above example, for loop incrementing “i” seems like not maintaining anything as invariant. But still we can tell the value of i at any point of time.
If the loop gets to stop in-between then, i’s value is nothing but the time when its stopped. But we don’t have the history.
Next example, array getting set to value of i. History of i is stored. At any point of time, we have data operation for each iteration.
Did you know?
Erlang is a kind of programming language where there is no concept of variables. :) Once we assign a value to the variable using assignment operator, next time it does plain comparison rather than re-assignment. Which means its a invariant variable. It’s not a constant as we see in C++. Don’t confuse with that anyway.
http://learnyousomeerlang.com/starting-out-for-real#invariable-variables

Tail recursion–in detail

“The beauty of recursion is that!!.. - the beauty of recursion.”

Author speaks

  Sorry for not publishing any post nowadays. Tied up with lots of personal work. Now, would love to continue the series without gaps at least for some time. This promise is Without any GURANTEE, WARENTEE or any BONDS. :)

Metaphor

  If you catch something by tail, it tries to attack you using its head. :D

I think the below image will make you remember very well what is tail recursion.

Introduction

   Tail recursion is something that is more native to functional programming languages. In Maths, a tail recursive function is a function that expands itself.

Say, g(x) = f(x)

Then, tail recursion happens like this formula,        f(x) = f(g(x))

This means, f(x) = f(f(x)) = g(f(f(x)) = f(f(f(x))) … it goes on

This is purely useful for writing an mathematical logic which has a specific end condition. But this kind of recursion is majorly used in optimization of stack space in C++ and similar languages. Even some dynamic languages support this recursion type. But python doesn’t support it because of simple inherent problems for developers while using tail recursion.

Concept

   As i explained, tail recursion is mostly used for optimization & mathematical problem and widely popular in functional programming. The most and the perfect way a tail recursion works is really good for designing mathematically a computer program. But if you are normal novice software engineer, you just use this for optimization and only when its necessary because of its demerits:

• Stack doesn’t contain any footprint of the recursion happening. Compiler tries to expand the cycling recursion into instructions without using stack
• As there is no stack data, no way to debug such programs easily.
• Compilers might sometime fail to make the right jumps and data corruption can never be captured.

Already developers fight with pointers when this havoc adds more headache to it.

Programmers can think tail recursion as, just processing things using arguments itself and keep the returned value as the recursive call to the function. This makes the compiler to process the return value which expands the recursive calls in the single stack frame!!

Code

#include <iostream>

int fib(int n)

{

    if(n==0)

        return 0;

    else if(n==1)

        return 1;

    else 

        return fib(n-1) + fib(n-2);

}

int main()

{

    std::cout<<fib(7);

    return 0;

}

• Assembly is generated with tail optimization only when release mode is selected with Visual Studio C++.
• You can note that there is no stack footprint by the executable created by this, by tracing the disassembly.

Conclusion

Is it good or bad? based on the need and stack space savings requirement.

Construct Single threaded binary tree–In-order successor connection

“The main advantage of threaded trees is the reduction in traversal time and space.. Tree traversal is really time consuming + stack space consuming. We can reduce that, if we have threaded the tree with the empty nodes at the bottom.”

Introduction

   Before diving into the concept behind this, understand and re-study the following links,

http://analgorithmaday.blogspot.com/2011/03/successor-and-predecessorbst.html

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

In this article, we will just see how to thread the tree so that, all the leaf nodes get connected to its in-order successor nodes. As its a successor node, we connect the right nodes to the appropriate root.

Concept

The important property of the in-order successor node is that,

• If the node you see has a NULL right node and the node is present as left child for its parent, simply connect the NULL node to the parent.
• If the node you see has a NULL right node but its a right child for its parent, then move to a parent for which our node is not the right!!

This is already discussed clearly in successor and predecessor. But how to do this with recursion and without a parent node part of the tree!!

Little bit tricky!!.. :) But if you understand that, you need to create cycles with the current parent. you will catch the way!!

i.e,

Consider you have a tree like this,

           

Firstly, you need to do recursion so that child gets connected to parent. That is,

7->3, 8->3, 3->1,9->4, 4->1.. etc.

After you get this recursion, connect 7->right to 3 and 8->right also to 3. But when you need to connect 3 to 1, you just check whether traversing 3->right->right gives again the 3.. :)

That is, 

          1

     3

7       8 –> right node connected to 3.

Between 3 and 8 there is a cycle, just detect this cycle and move the 8-th right node to the parent of 3. which is 1. :)

The above is what we need to achieve to get the in-order successor.

Code

Tree* makeThreaded(Tree* root)

{

    if(root == NULL)

        return NULL;

    Tree* leftPrev = makeThreaded(root->left);

    if(leftPrev != NULL) {

        std::cout<<leftPrev->data;

        std::cout<<":"<<root->data<<std::endl;

        Tree* iter = leftPrev;

        while(iter->right != NULL && iter->right != leftPrev)

            iter = iter->right;

        iter->right = root;

    }

    Tree* rightPrev = makeThreaded(root->right);

    if(rightPrev != NULL) {

        std::cout<<rightPrev->data;

        std::cout<<":"<<root->data<<std::endl;

        Tree* iter = rightPrev;

        while(iter->right != NULL && iter->right != rightPrev)

            iter = iter->right;

        iter->right = root;

    }

    return root;

}

Tree* tobj = newTree();

Tree* root = makeThreaded(tobj); // there will be no change in root

• we need to iterate until we find the right!!.. That’s why we need that for loop.
• we don’t use any extra space in this algorithm. We reuse the NULL nodes in the tree.
• We don’t have any difference between threaded node and normal node. :) We can traverse as usual.

Counting number of nodes in a binary tree

 

Introduction

   How would you count the number of nodes in a tree? Traverse all the nodes in a tree. You can do any traversal and just start counting. But there is a concept called tail recursion which is handy and very easily readable.

If you have a tree, if you know the number of nodes in the left and number of nodes in right +1, then, what you get is total number of nodes.

Concept

   You have to do tail recursion with count(root->left) + count(root->right)+1.

After you get the count, how you will find the height of the tree ?

  log₂ count_of_nodes. But in C++, you won’t get a function to calculate log base 2. :)

There is a way,

  log₁₀ n/log ₁₀ 2 = log ₂ n

So, you just need to use the above formula to get log base 2 which yields the height of the tree.

Code

Tree* tobj;

int count(Tree* root) {

    if(root == NULL)

        return 0;

    else 

        if(root->left == NULL && root->right == NULL)

            return 1;

        else

            return count(root->left) + count(root->right) + 1;    

}

cout<<count(tobj);

• you are covering 2 base conditions here, root == NULL then 0. root->left & root->right is NULL, then only root node is there, which is 1.
• This expands to 1 for each node in the left & right.

Level order insert in a binary tree

“We have seen binary search trees, heaps.. how would you normally create a dynamic tree from a list. Simply, you are given an array, you need to convert it into a binary tree in level order.”

Introduction

    Level order traversal needs a level-by-level movement in a tree. But if you want to recreate the tree from an array in a level-order way. It should be easy. Just you need to fill the elements with the correct formula as we already discussed.

       2i             -----> root

2i+1     2i+2    --> left      right

This is the basis for the level order insert.

Concept

   If you check the level order traversal, many uses stacks. But we should avoid using stacks. Instead, we will use recursion for our case.

  Understanding recursion requires a simple base condition which needs to be repeated for different argument.

     for example, if you have an array,

     arr = {0,1,2,3,4,5,6,7,8,9}

the tree becomes like this,

                  0

           1                    2

    3           4           5      6

7     8     9

For 0, we need to create 1 and 2. For 1, 3, 4. For 3, create 7,8. Similarly for 4, create 9.

This means, you need to do recursion left with left index and right with right index. The end condition is when left or right index is exceeding the size of the array.

Code

Tree *tobj;

void level_order_insert(Tree* root, int* arr, int start, int size)

{

    int left = 2*start+1;

    int right = 2*start+2;

    if(left > size || right > size)

        return;

    if(root == NULL) {

        tobj = createNode(arr[start]);

        root = tobj;

    }

    if(root->left == NULL && root->right == NULL) {

        if(left < size)

            root->left = createNode(arr[left]);

        if(right < size)

            root->right = createNode(arr[right]);

    }

    level_order_insert(root->left, arr, left, size);

    level_order_insert(root->right, arr, right, size);

}

main() {

   int A[] = {0,1,2,3,4,5,6,7,8,9}

   level_order_insert(tobj, A, 0, 10);

}

• Before root->left = createNode. You need to make sure that left is still < size. This is to handle the border case
• root->left gets start as all left with all odd numbers
• root->right gets start as all right with all even numbers.
• Most of the times you get partially balanced tree with this method.