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

Mirror a binary tree

 

Introduction

  Mirroring a binary tree, a common question nowadays to understand whether the candidate knows about tree traversal. Asking plainly in-order/pre-order is of no use!! :)

 

Solution 

The dummies way is to directly jump to code which never works even for such a simple problem.

First thought, i got this code:

Tree* mirror(Tree* node)

{

    if(node == NULL)

        return NULL;

    node->left = mirror(node->right);

    node->right = mirror(node->left);

    return node;

} 

Flaws in it?

- This is a mugged up code!!

- You didn’t think about whether to output the mirrored tree in a new data structure or to do it in-place

- Why you cannot use tail recursion for in-place,

- Reason 1: you need to swap left & right using a temporary storage. You need to expand the tree on the stack

- Reason 2: The above kind of swapping loses the node->left data whatever magic your recursion does.

 

Now, we got full of issues, think basic, non-iterative way

tmp = tree->left;

tree->left = tree->right;

tree->right = tmp;

Whatever way you follow, you need to do the above swap.

Corrected code for reproduction of mirrored tree, as a copy

Tree* mirror(Tree* node)

{

    if(node == NULL)

        return NULL;

    Tree *newNode = createNode(node->data);

    newNode->left = mirror(node->right);

    newNode->right = mirror(node->left);

    return newNode;

}

Correct code for creating mirrored tree, in-place

- do a post order traversal to read the full tree into the recursion stack

- do the primitive swap operation

Tree* mirror(Tree* node)

{

    if(node == NULL)

        return NULL;

    mirror(node->left);

    mirror(node->right);

    Tree *tmp = node->left;

    node->left = node->right;

    node->right = tmp;

    return node;

}

Searching BST

“Scanning through an English dictionary is faster because, you directly go to the indexed character and scan through letter one-by-one to get to the exact text you are searching for”

Preface

  Sorry for not updating for a long period of around 5 months. Really struck up with busy schedules. Now I forgot all the data structures and algorithms. So need to relearn and hence will revisit all my previous posts before going into medium difficulty content.

References

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

Introduction

  How would you design a search algorithm which does a search through the English dictionary in really fast manner?  Manually, you can easily check a dictionary based on lexicographic ordering. But how would you design a data structure which can naturally allow you to do that? you can do this with a binary search tree.

In previous article, we learnt about Hash Tables(http://analgorithmaday.blogspot.in/2011/10/hash-tables-dictionaries.html) that it is an array index to data mapping. This is a direct mapping hash table which can be generically implemented using binary search trees. If you check the implementations of map and hash_map in C++ STLs, these are implemented using a kind of binary search trees.

Concept

   We decide left or right of the binary search tree based on the value we need to search for. It reduces loops logarithmically.

  Bonus: We can also check how to get the 4th smallest element out of the binary search tree.  This can be done by having an extra field which can calculate the rank of the node.

Rank of a node in BST is number of nodes in the left sub-tree + 1. This is nothing but number of keys less than the current value. This rank is helpful to identify the successor and predecessor easily.

If space is not a constraint, then we should go with ranking the nodes. But if its a constraint, then you should identify the successor of each node

Code

Searching a binary search tree (iteration)

class BST {

public:

    int data;

    BST* parent;

    BST* left;

    BST* right;

};

BST* createBSTNode(int data)

{

    BST* newNode = new BST();

    newNode->data = data;

    newNode->left = NULL;

    newNode->right = NULL;

    newNode->parent = NULL;

    return newNode;

}

void bst_insert(BST*& tree, BST* node)

{

    BST* prev = NULL;

    BST* iter=tree;

    while(iter != NULL)

    {

        prev = iter;

        if(node->data > iter->data)

            iter = iter->left;

        else

            iter = iter->right;

    }

    // found node is parent to our node

    node->parent = prev;

    // if prev is NULL

    // then this is the first node

    // change the root NODE

    if(prev == NULL)

        tree = node;

    else {

        // now we need to decide where the node

        // should go: left or right

        if(node->data > prev->data)

            prev->left = node;

        else

            prev->right = node;

    }

}

BST* convert_arr_bst(int* arr, int size)

{

    BST* tree=NULL;

    for(int i=0;i<size;i++) {

        bst_insert(tree, createBSTNode(arr[i]));

    }

    return tree;

}

void main()

{

    BST *tree, *tmp;

    int k = 6;

    bool found = false;

    int arr[]= {2,30,12,10,22,6};

    tree = convert_arr_bst(arr, 6);

    tmp = tree;

    while(tmp && !found)

    {

        if(tmp->data == k) found = true;

        if(tmp->data < k) tmp = tmp->left;

        else {

            tmp = tmp->right;

        }

    }

    if(found == true)

        cout<<"Found"<<endl;

    else

        cout<<"Not Found"<<endl;

}

Searching a binary search tree based on ranks

Will see this in next article about constructing binary search trees with ranks.

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.