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\n" ; printInorder(root); replaceNode(root); cout << endl; cout << "After Replacing Nodes\n" ; 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 print inorder # 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 |
Javascript
<script> // JavaScript program to replace every // key value with its depth. class Node { constructor(data) { this .left = null ; this .right = null ; this .data = data; } } /* Utility function to create a new Binary Tree node */ function newNode(data) { let temp = new Node(data); return temp; } // Helper function replaces the data with depth // Note : Default value of level is 0 for root. function replaceNode(node, 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 function printInorder(node) { if (node == null ) return ; printInorder(node.left); document.write(node.data + " " ); printInorder(node.right); } let 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); document.write( "Before Replacing Nodes" + "</br>" ); printInorder(root); replaceNode(root, 0); document.write( "</br>" ); document.write( "</br>" ); document.write( "After Replacing Nodes" + "</br>" ); printInorder(root); </script> |
Before Replacing Nodes 1 2 4 3 5 After Replacing Nodes 2 1 2 0 1
Time Complexity: O(n)
Space Complexity: If we don’t consider size of stack for function calls then O(1) otherwise O(h)
Iterative Approach(Using Queue data structure):
Follow the below steps to solve the above problem:
1) Perform level order traversal with the help of queue data structure.
2) At each level keep track to level(indexing 0) and replace all nodes data of current level to level value.
3) Print the Inorder traversal of resultant tree.
Below is the implementation of above approach:
C++
// C++ Program to replace every node data // with its depth #include<bits/stdc++.h> using namespace std; // a tree node struct Node{ int data; struct Node *left, *right; }; // utility function to create a new 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* root){ // base case if (root == NULL) return ; queue<Node*> q; int level = 0; q.push(root); while (!q.empty()){ int n = q.size(); for ( int i = 0; i<n; i++){ Node* front_node = q.front(); q.pop(); front_node->data = level; if (front_node->left) q.push(front_node->left); if (front_node->right) q.push(front_node->right); } level++; } } // 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; 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; } // THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
Java
// Java Program to replace every node data with its depth import java.io.*; import java.util.*; class Node { int data; Node left, right; } class GFG { // utility function to create a new node static 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. static void replaceNode(Node root) { // base case if (root == null ) return ; Queue<Node> q = new LinkedList<>(); int level = 0 ; q.add(root); while (!q.isEmpty()) { int n = q.size(); for ( int i = 0 ; i < n; i++) { Node frontNode = q.poll(); frontNode.data = level; if (frontNode.left != null ) q.add(frontNode.left); if (frontNode.right != null ) q.add(frontNode.right); } level++; } } // 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); } public static void main(String[] args) { Node 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); System.out.println(); System.out.println( "After Replacing Nodes" ); printInorder(root); } } // This code is contributed by karthik. |
Python3
# Python program to replace every node data # with its depth # a tree node class Node: def __init__( self , data): self .data = data self .left = None self .right = None # Helper function replaces the data with depth # Note : Default value of level is 0 for root. def replaceNode(root): # base case if root is None : return queue = [] level = 0 queue.append(root) while queue: n = len (queue) for i in range (n): front_node = queue.pop( 0 ) front_node.data = level if front_node.left: queue.append(front_node.left) if front_node.right: queue.append(front_node.right) level + = 1 # A utility function to print inorder # traversal of a Binary Tree def printInorder(node): if node is None : return printInorder(node.left) print (node.data, end = " " ) printInorder(node.right) # Driver function to test above functions if __name__ = = '__main__' : root = Node( 3 ) root.left = Node( 2 ) root.right = Node( 5 ) root.left.left = Node( 1 ) root.left.right = Node( 4 ) print ( "Before Replacing Nodes" ) printInorder(root) replaceNode(root) print () print ( "After Replacing Nodes" ) printInorder(root) |
C#
// C# Program to replace every node data with its depth using System; using System.Collections.Generic; class Node { public int data; public Node left, right; } public class GFG { // utility function to create a new node static 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. static void replaceNode(Node root) { // base case if (root == null ) return ; Queue<Node> q = new Queue<Node>(); int level = 0; q.Enqueue(root); while (q.Count > 0) { int n = q.Count; for ( int i = 0; i < n; i++) { Node frontNode = q.Dequeue(); frontNode.data = level; if (frontNode.left != null ) q.Enqueue(frontNode.left); if (frontNode.right != null ) q.Enqueue(frontNode.right); } level++; } } // 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); } static public void Main() { // Code Node 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); Console.WriteLine(); Console.WriteLine( "After Replacing Nodes" ); printInorder(root); } } // This code is contributed by sankar. |
Javascript
// JavaScript program to replace every node data // with its depth // a trree node class Node{ constructor(data){ this .data = data; this .left = this .right = null ; } } // utility function to create a new node function newNode(data){ return new Node(data); } // Helper function replaces the data with depth // Note : Default value of level is 0 for root. function replaceNode(root){ // base case if (root == null ) return ; let q = []; let level = 0; q.push(root); while (q.length > 0){ let n = q.length; for (let i = 0; i<n; i++){ let front_node = q.shift(); front_node.data = level; if (front_node.left) q.push(front_node.left); if (front_node.right) q.push(front_node.right); } level++; } } // A utility function to print inorder // traversal of a Binary Tree function printInorder(node){ if (node == null ) return ; printInorder(node.left); console.log(node.data + " " ); printInorder(node.right); } // driver function to test above functions let root = newNode(3); root.left = newNode(2); root.right = newNode(5); root.left.left = newNode(1); root.left.right = newNode(4); console.log( "Before replacing Nodes : " ); printInorder(root); replaceNode(root); console.log( "After replacing Nodes : " ); printInorder(root); |
Before Replacing Nodes 1 2 4 3 5 After Replacing Nodes 2 1 2 0 1
Time Complexity: O(N) where N is the number of nodes in given binary tree
Auxiliary Space: O(N) due to queue data structure