Replace node with depth in a binary tree

Given a binary tree, replace each node with its depth value. For example, consider the following tree. Root is at depth 0, change its value to 0 and next level nodes are at depth 1 and so on.

       3                       0
      /  \                    /   \
     2    5      == >;         1     1
   /   \                   /   \
  1     4                 2     2

The idea is to traverse tree starting from root. While traversing pass depth of node as parameter. We can track depth by passing it as 0 for root and one-plus-current-depth for children.

Below is C++ implementation of the idea.

// CPP program to replace every key value
// with its depth.
#include<bits/stdc++.h>
using namespace std;
/* A tree node structure */
struct Node
{
    int data;
    struct Node *left, *right;
};
/* Utility function to create a
   new Binary Tree node */
struct Node* newNode(int data)
{
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;   
    return temp;
}
// Helper function replaces the data with depth
// Note : Default value of level is 0 for root.
void replaceNode(struct Node *node, int level=0)
{
    // Base Case
    if (node == NULL)
        return;
    // Replace data with current depth
    node->data = level;
    replaceNode(node->left, level+1);
    replaceNode(node->right, level+1);
}
// A utility function to print inorder
// traversal of a Binary Tree
void printInorder(struct Node* node)
{
     if (node == NULL)
          return;
     printInorder(node->left);
     cout << node->data <<" ";
     printInorder(node->right);
}
/* Driver function to test above functions */
int main()
{
    struct Node *root = new struct Node;
    /* Constructing tree given in
       the above figure */
    root = newNode(3);
    root->left = newNode(2);
    root->right = newNode(5);
    root->left->left = newNode(1);
    root->left->right = newNode(4);
    
    cout << "Before Replacing Nodes\n";   
    printInorder(root);
    replaceNode(root); 
    cout << endl;
    
    cout << "After Replacing Nodes\n";
    printInorder(root);
    
    return 0;
}

Output:

Before Replacing Nodes
1 2 4 3 5 

After Replacing Nodes
2 1 2 0 1 

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar