Tutorialspoint.dev

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 the implementation of the idea.

C++

// 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 ";    
    printInorder(root);
    replaceNode(root);  
    cout << endl;
      
    cout << "After Replacing Nodes ";
    printInorder(root);
      
    return 0;
}

Java

// Java program to replace every key value 
// with its depth. 
class GfG { 
  
/* A tree node structure */
static class Node 
    int data; 
    Node left, right; 
}
  
/* Utility function to create a 
new Binary Tree node */
static Node newNode(int data) 
    Node temp = new Node(); 
    temp.data = data; 
    temp.left = null;
    temp.right = null;     
    return temp; 
  
// Helper function replaces the data with depth 
// Note : Default value of level is 0 for root. 
static void replaceNode(Node node, int level) 
    // 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 
static void printInorder(Node node) 
    if (node == null
        return
    printInorder(node.left); 
    System.out.print(node.data + " "); 
    printInorder(node.right); 
  
/* Driver function to test above functions */
public static void main(String[] args) 
    Node root = new 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); 
      
    System.out.println("Before Replacing Nodes");     
    printInorder(root); 
    replaceNode(root, 0); 
    System.out.println();
      
    System.out.println("After Replacing Nodes"); 
    printInorder(root); 
      
}

Python3

# Python3 program to replace every key 
# value with its depth. 
  
class newNode:
    def __init__(self, data):
        self.data = data 
        self.left = self.right = None
  
# Helper function replaces the data with depth 
# Note : Default value of level is 0 for root. 
def replaceNode(node, level = 0):
      
    # Base Case 
    if (node == None):
        return
  
    # Replace data with current depth 
    node.data = level 
  
    replaceNode(node.left, level + 1
    replaceNode(node.right, level + 1)
  
# A utility function to prinorder 
# traversal of a Binary Tree 
def printInorder(node):
    if (node == None): 
        return
    printInorder(node.left) 
    print(node.data, end = " ")
    printInorder(node.right)
  
# Driver Code
if __name__ == '__main__':
  
    # 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
      
    print("Before Replacing Nodes")     
    printInorder(root) 
    replaceNode(root) 
      
    print()
    print("After Replacing Nodes"
    printInorder(root)
  
# This code is contributed by PranchalK

C#

// C# program to replace every key value 
// with its depth. 
using System;
  
public class GfG 
  
    /* A tree node structure */
    public class Node 
    
        public int data; 
        public Node left, right; 
    }
  
    /* Utility function to create a 
    new Binary Tree node */
    static Node newNode(int data) 
    
        Node temp = new Node(); 
        temp.data = data; 
        temp.left = null;
        temp.right = null;   
        return temp; 
    
  
    // Helper function replaces the data with depth 
    // Note : Default value of level is 0 for root. 
    static void replaceNode(Node node, int level) 
    
        // 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 
    static void printInorder(Node node) 
    
        if (node == null
            return
        printInorder(node.left); 
        Console.Write(node.data + " "); 
        printInorder(node.right); 
    
  
    /* Driver code*/
    public static void Main(String[] args) 
    
        Node root = new 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); 
  
        Console.WriteLine("Before Replacing Nodes");     
        printInorder(root); 
        replaceNode(root, 0); 
        Console.WriteLine();
  
        Console.WriteLine("After Replacing Nodes"); 
        printInorder(root); 
    }
}
  
// This code is contributed Rajput-Ji 


Output:

Before Replacing Nodes
1 2 4 3 5 

After Replacing Nodes
2 1 2 0 1 

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

tags:

Tree Tree

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter