Replace node with depth in a binary tree
The given problem is to replace the value of each node in a binary tree with its depth (or level) in the tree. The depth of a node is the length of the path from the root to that node. The root node has a depth of 0, its children have a depth of 1, their children have a depth of 2, and so on. The goal is to traverse the entire binary tree and replace each node's value with its corresponding depth.
Example
Let's consider a binary tree as shown below:
4
/ \
12 7
/ \ \
2 3 1
/ \ /
6 8 5
/
9
The initial values of the nodes are: [4, 12, 2, 3, 6, 9, 8, 7, 1, 5]
Pseudocode
1. ReplaceNodeWithDepth(node, depth):
2. if node is NULL:
3. return
4. node.data = depth
5. ReplaceNodeWithDepth(node.left, depth + 1)
6. ReplaceNodeWithDepth(node.right, depth + 1)
Algorithm Explanation
- We start with a recursive function
ReplaceNodeWithDepth
, which takes two parameters:node
(the current node to process) anddepth
(the depth of the current node). - If the
node
is NULL, we have reached a leaf node or an empty subtree, so we return from the current call. - Otherwise, we update the
node
's data with the current depth value. - Then, we make recursive calls to
ReplaceNodeWithDepth
for the left and right subtrees with an incremented depth value (depth + 1). - The recursion will traverse the entire binary tree and replace each node's value with its depth.
Code Solution
Here given code implementation process.
// C program for
// Replace node with depth in a binary tree
#include <stdio.h>
#include <stdlib.h>
// Tree Node
struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};
// Binary Tree
struct BinaryTree
{
struct TreeNode *root;
};
// Create new tree
struct BinaryTree *newTree()
{
// Create a dynamic tree
struct BinaryTree *tree =
(struct BinaryTree *) malloc(sizeof(struct BinaryTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
//return new tree
return tree;
}
// This is creates and returns the new binary tree node
struct TreeNode *getNode(int data)
{
// Create dynamic node
struct TreeNode *node =
(struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
//Set data and pointer values
node->data = data;
node->left = NULL;
node->right = NULL;
}
else
{
//This is indicates, segmentation fault
// or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return node;
}
void preOrder(struct TreeNode *node)
{
if (node != NULL)
{
// Print node value
printf(" %d", node->data);
// Visit left subtree
preOrder(node->left);
// Visit right subtree
preOrder(node->right);
}
}
void replaceByDepth(struct TreeNode *node, int depth)
{
if (node != NULL)
{
// Change node value
node->data = depth;
// Visit left subtree
replaceByDepth(node->left, depth + 1);
// Visit right subtree
replaceByDepth(node->right, depth + 1);
}
}
int main(int argc, char const *argv[])
{
struct BinaryTree *tree = newTree();
/*
4
/ \
12 7
/ \ \
2 3 1
/ \ /
6 8 5
/
9
-----------------
Constructing binary tree
*/
tree->root = getNode(4);
tree->root->left = getNode(12);
tree->root->left->right = getNode(3);
tree->root->left->right->left = getNode(6);
tree->root->left->right->left->left = getNode(9);
tree->root->left->right->right = getNode(8);
tree->root->left->left = getNode(2);
tree->root->right = getNode(7);
tree->root->right->right = getNode(1);
tree->root->right->right->left = getNode(5);
printf("\n Before replace by depth \n");
preOrder(tree->root);
// Update node value by depth
replaceByDepth(tree->root, 0);
printf("\n After replace by depth \n");
preOrder(tree->root);
return 0;
}
input
Before replace by depth
4 12 2 3 6 9 8 7 1 5
After replace by depth
0 1 2 2 3 4 3 1 2 3
/*
Java Program
Replace node with depth in a binary tree
*/
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
public void preOrder(TreeNode node)
{
if (node != null)
{
// Print node value
System.out.print(" " + node.data );
// Visit left subtree
preOrder(node.left);
// Visit right subtree
preOrder(node.right);
}
}
public void replaceByDepth(TreeNode node, int depth)
{
if (node != null)
{
// Change node value
node.data = depth;
// Visit left subtree
replaceByDepth(node.left, depth + 1);
// Visit right subtree
replaceByDepth(node.right, depth + 1);
}
}
public static void main(String[] args)
{
// Create new binary tree
BinaryTree tree = new BinaryTree();
/*
4
/ \
12 7
/ \ \
2 3 1
/ \ /
6 8 5
/
9
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(12);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(1);
tree.root.right.right.left = new TreeNode(5);
System.out.print("\n Before replace by depth \n");
tree.preOrder(tree.root);
// Update node value by depth
tree.replaceByDepth(tree.root, 0);
System.out.print("\n After replace by depth \n");
tree.preOrder(tree.root);
}
}
input
Before replace by depth
4 12 2 3 6 9 8 7 1 5
After replace by depth
0 1 2 2 3 4 3 1 2 3
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Replace node with depth in a binary tree
*/
// Binary Tree node
class TreeNode
{
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public:
TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
void preOrder(TreeNode *node)
{
if (node != NULL)
{
// Print node value
cout << " " << node->data;
// Visit left subtree
this->preOrder(node->left);
// Visit right subtree
this->preOrder(node->right);
}
}
void replaceByDepth(TreeNode *node, int depth)
{
if (node != NULL)
{
// Change node value
node->data = depth;
// Visit left subtree
this->replaceByDepth(node->left, depth + 1);
// Visit right subtree
this->replaceByDepth(node->right, depth + 1);
}
}
};
int main()
{
// Create new binary tree
BinaryTree *tree = new BinaryTree();
/*
4
/ \
12 7
/ \ \
2 3 1
/ \ /
6 8 5
/
9
-----------------
Constructing binary tree
*/
tree->root = new TreeNode(4);
tree->root->left = new TreeNode(12);
tree->root->left->right = new TreeNode(3);
tree->root->left->right->left = new TreeNode(6);
tree->root->left->right->left->left = new TreeNode(9);
tree->root->left->right->right = new TreeNode(8);
tree->root->left->left = new TreeNode(2);
tree->root->right = new TreeNode(7);
tree->root->right->right = new TreeNode(1);
tree->root->right->right->left = new TreeNode(5);
cout << "\n Before replace by depth \n";
tree->preOrder(tree->root);
// Update node value by depth
tree->replaceByDepth(tree->root, 0);
cout << "\n After replace by depth \n";
tree->preOrder(tree->root);
return 0;
}
input
Before replace by depth
4 12 2 3 6 9 8 7 1 5
After replace by depth
0 1 2 2 3 4 3 1 2 3
// Include namespace system
using System;
/*
Csharp Program
Replace node with depth in a binary tree
*/
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
public void preOrder(TreeNode node)
{
if (node != null)
{
// Print node value
Console.Write(" " + node.data);
// Visit left subtree
this.preOrder(node.left);
// Visit right subtree
this.preOrder(node.right);
}
}
public void replaceByDepth(TreeNode node, int depth)
{
if (node != null)
{
// Change node value
node.data = depth;
// Visit left subtree
this.replaceByDepth(node.left, depth + 1);
// Visit right subtree
this.replaceByDepth(node.right, depth + 1);
}
}
public static void Main(String[] args)
{
// Create new binary tree
BinaryTree tree = new BinaryTree();
/*
4
/ \
12 7
/ \ \
2 3 1
/ \ /
6 8 5
/
9
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(12);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(1);
tree.root.right.right.left = new TreeNode(5);
Console.Write("\n Before replace by depth \n");
tree.preOrder(tree.root);
// Update node value by depth
tree.replaceByDepth(tree.root, 0);
Console.Write("\n After replace by depth \n");
tree.preOrder(tree.root);
}
}
input
Before replace by depth
4 12 2 3 6 9 8 7 1 5
After replace by depth
0 1 2 2 3 4 3 1 2 3
<?php
/*
Php Program
Replace node with depth in a binary tree
*/
// Binary Tree node
class TreeNode
{
public $data;
public $left;
public $right;
public function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
}
class BinaryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
public function preOrder($node)
{
if ($node != NULL)
{
// Print node value
echo(" ".$node->data);
// Visit left subtree
$this->preOrder($node->left);
// Visit right subtree
$this->preOrder($node->right);
}
}
public function replaceByDepth($node, $depth)
{
if ($node != NULL)
{
// Change node value
$node->data = $depth;
// Visit left subtree
$this->replaceByDepth($node->left, $depth + 1);
// Visit right subtree
$this->replaceByDepth($node->right, $depth + 1);
}
}
}
function main()
{
// Create new binary tree
$tree = new BinaryTree();
/*
4
/ \
12 7
/ \ \
2 3 1
/ \ /
6 8 5
/
9
-----------------
Constructing binary tree
*/
$tree->root = new TreeNode(4);
$tree->root->left = new TreeNode(12);
$tree->root->left->right = new TreeNode(3);
$tree->root->left->right->left = new TreeNode(6);
$tree->root->left->right->left->left = new TreeNode(9);
$tree->root->left->right->right = new TreeNode(8);
$tree->root->left->left = new TreeNode(2);
$tree->root->right = new TreeNode(7);
$tree->root->right->right = new TreeNode(1);
$tree->root->right->right->left = new TreeNode(5);
echo("\n Before replace by depth \n");
$tree->preOrder($tree->root);
// Update node value by depth
$tree->replaceByDepth($tree->root, 0);
echo("\n After replace by depth \n");
$tree->preOrder($tree->root);
}
main();
input
Before replace by depth
4 12 2 3 6 9 8 7 1 5
After replace by depth
0 1 2 2 3 4 3 1 2 3
/*
Node JS Program
Replace node with depth in a binary tree
*/
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
preOrder(node)
{
if (node != null)
{
// Print node value
process.stdout.write(" " + node.data);
// Visit left subtree
this.preOrder(node.left);
// Visit right subtree
this.preOrder(node.right);
}
}
replaceByDepth(node, depth)
{
if (node != null)
{
// Change node value
node.data = depth;
// Visit left subtree
this.replaceByDepth(node.left, depth + 1);
// Visit right subtree
this.replaceByDepth(node.right, depth + 1);
}
}
}
function main()
{
// Create new binary tree
var tree = new BinaryTree();
/*
4
/ \
12 7
/ \ \
2 3 1
/ \ /
6 8 5
/
9
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(12);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(1);
tree.root.right.right.left = new TreeNode(5);
process.stdout.write("\n Before replace by depth \n");
tree.preOrder(tree.root);
// Update node value by depth
tree.replaceByDepth(tree.root, 0);
process.stdout.write("\n After replace by depth \n");
tree.preOrder(tree.root);
}
main();
input
Before replace by depth
4 12 2 3 6 9 8 7 1 5
After replace by depth
0 1 2 2 3 4 3 1 2 3
# Python 3 Program
# Replace node with depth in a binary tree
# Binary Tree node
class TreeNode :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
self.root = None
def preOrder(self, node) :
if (node != None) :
# Print node value
print(" ", node.data, end = "")
# Visit left subtree
self.preOrder(node.left)
# Visit right subtree
self.preOrder(node.right)
def replaceByDepth(self, node, depth) :
if (node != None) :
# Change node value
node.data = depth
# Visit left subtree
self.replaceByDepth(node.left, depth + 1)
# Visit right subtree
self.replaceByDepth(node.right, depth + 1)
def main() :
# Create new binary tree
tree = BinaryTree()
# 4
# / \
# 12 7
# / \ \
# 2 3 1
# / \ /
# 6 8 5
# /
# 9
# -----------------
# Constructing binary tree
tree.root = TreeNode(4)
tree.root.left = TreeNode(12)
tree.root.left.right = TreeNode(3)
tree.root.left.right.left = TreeNode(6)
tree.root.left.right.left.left = TreeNode(9)
tree.root.left.right.right = TreeNode(8)
tree.root.left.left = TreeNode(2)
tree.root.right = TreeNode(7)
tree.root.right.right = TreeNode(1)
tree.root.right.right.left = TreeNode(5)
print("\n Before replace by depth ")
tree.preOrder(tree.root)
# Update node value by depth
tree.replaceByDepth(tree.root, 0)
print("\n After replace by depth ")
tree.preOrder(tree.root)
if __name__ == "__main__": main()
input
Before replace by depth
4 12 2 3 6 9 8 7 1 5
After replace by depth
0 1 2 2 3 4 3 1 2 3
# Ruby Program
# Replace node with depth in a binary tree
# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# Set node value
self.data = data
self.left = nil
self.right = nil
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
def preOrder(node)
if (node != nil)
# Print node value
print(" ", node.data)
# Visit left subtree
self.preOrder(node.left)
# Visit right subtree
self.preOrder(node.right)
end
end
def replaceByDepth(node, depth)
if (node != nil)
# Change node value
node.data = depth
# Visit left subtree
self.replaceByDepth(node.left, depth + 1)
# Visit right subtree
self.replaceByDepth(node.right, depth + 1)
end
end
end
def main()
# Create new binary tree
tree = BinaryTree.new()
# 4
# / \
# 12 7
# / \ \
# 2 3 1
# / \ /
# 6 8 5
# /
# 9
# -----------------
# Constructing binary tree
tree.root = TreeNode.new(4)
tree.root.left = TreeNode.new(12)
tree.root.left.right = TreeNode.new(3)
tree.root.left.right.left = TreeNode.new(6)
tree.root.left.right.left.left = TreeNode.new(9)
tree.root.left.right.right = TreeNode.new(8)
tree.root.left.left = TreeNode.new(2)
tree.root.right = TreeNode.new(7)
tree.root.right.right = TreeNode.new(1)
tree.root.right.right.left = TreeNode.new(5)
print("\n Before replace by depth \n")
tree.preOrder(tree.root)
# Update node value by depth
tree.replaceByDepth(tree.root, 0)
print("\n After replace by depth \n")
tree.preOrder(tree.root)
end
main()
input
Before replace by depth
4 12 2 3 6 9 8 7 1 5
After replace by depth
0 1 2 2 3 4 3 1 2 3
/*
Scala Program
Replace node with depth in a binary tree
*/
// Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data,null,null);
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def preOrder(node: TreeNode): Unit = {
if (node != null)
{
// Print node value
print(" " + node.data);
// Visit left subtree
preOrder(node.left);
// Visit right subtree
preOrder(node.right);
}
}
def replaceByDepth(node: TreeNode, depth: Int): Unit = {
if (node != null)
{
// Change node value
node.data = depth;
// Visit left subtree
replaceByDepth(node.left, depth + 1);
// Visit right subtree
replaceByDepth(node.right, depth + 1);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create new binary tree
var tree: BinaryTree = new BinaryTree();
/*
4
/ \
12 7
/ \ \
2 3 1
/ \ /
6 8 5
/
9
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(12);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(6);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.left.right.right = new TreeNode(8);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(1);
tree.root.right.right.left = new TreeNode(5);
print("\n Before replace by depth \n");
tree.preOrder(tree.root);
// Update node value by depth
tree.replaceByDepth(tree.root, 0);
print("\n After replace by depth \n");
tree.preOrder(tree.root);
}
}
input
Before replace by depth
4 12 2 3 6 9 8 7 1 5
After replace by depth
0 1 2 2 3 4 3 1 2 3
/*
Swift 4 Program
Replace node with depth in a binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func preOrder(_ node: TreeNode? )
{
if (node != nil)
{
// Print node value
print(" ", node!.data, terminator: "");
// Visit left subtree
self.preOrder(node!.left);
// Visit right subtree
self.preOrder(node!.right);
}
}
func replaceByDepth(_ node: TreeNode? , _ depth : Int)
{
if (node != nil)
{
// Change node value
node!.data = depth;
// Visit left subtree
self.replaceByDepth(node!.left, depth + 1);
// Visit right subtree
self.replaceByDepth(node!.right, depth + 1);
}
}
}
func main()
{
// Create new binary tree
let tree = BinaryTree();
/*
4
/ \
12 7
/ \ \
2 3 1
/ \ /
6 8 5
/
9
-----------------
Constructing binary tree
*/
tree.root = TreeNode(4);
tree.root!.left = TreeNode(12);
tree.root!.left!.right = TreeNode(3);
tree.root!.left!.right!.left = TreeNode(6);
tree.root!.left!.right!.left!.left = TreeNode(9);
tree.root!.left!.right!.right = TreeNode(8);
tree.root!.left!.left = TreeNode(2);
tree.root!.right = TreeNode(7);
tree.root!.right!.right = TreeNode(1);
tree.root!.right!.right!.left = TreeNode(5);
print("\n Before replace by depth ");
tree.preOrder(tree.root);
// Update node value by depth
tree.replaceByDepth(tree.root, 0);
print("\n After replace by depth ");
tree.preOrder(tree.root);
}
main();
input
Before replace by depth
4 12 2 3 6 9 8 7 1 5
After replace by depth
0 1 2 2 3 4 3 1 2 3
/*
Kotlin Program
Replace node with depth in a binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun preOrder(node: TreeNode ? ): Unit
{
if (node != null)
{
// Print node value
print(" " + node.data);
// Visit left subtree
this.preOrder(node.left);
// Visit right subtree
this.preOrder(node.right);
}
}
fun replaceByDepth(node: TreeNode ? , depth : Int): Unit
{
if (node != null)
{
// Change node value
node.data = depth;
// Visit left subtree
this.replaceByDepth(node.left, depth + 1);
// Visit right subtree
this.replaceByDepth(node.right, depth + 1);
}
}
}
fun main(args: Array < String > ): Unit
{
// Create new binary tree
val tree: BinaryTree = BinaryTree();
/*
4
/ \
12 7
/ \ \
2 3 1
/ \ /
6 8 5
/
9
-----------------
Constructing binary tree
*/
tree.root = TreeNode(4);
tree.root?.left = TreeNode(12);
tree.root?.left?.right = TreeNode(3);
tree.root?.left?.right?.left = TreeNode(6);
tree.root?.left?.right?.left?.left = TreeNode(9);
tree.root?.left?.right?.right = TreeNode(8);
tree.root?.left?.left = TreeNode(2);
tree.root?.right = TreeNode(7);
tree.root?.right?.right = TreeNode(1);
tree.root?.right?.right?.left = TreeNode(5);
print("\n Before replace by depth \n");
tree.preOrder(tree.root);
// Update node value by depth
tree.replaceByDepth(tree.root, 0);
print("\n After replace by depth \n");
tree.preOrder(tree.root);
}
input
Before replace by depth
4 12 2 3 6 9 8 7 1 5
After replace by depth
0 1 2 2 3 4 3 1 2 3
Time Complexity
The time complexity of this algorithm is O(N), where N is the number of nodes in the binary tree. This is because we visit each node once during the traversal.
Resultant Output Explanation
After replacing the node values with their depths, the binary tree will look like this:
0
/ \
1 1
/ \ \
2 2 2
/ \ /
3 3 3
/
4
The new values of the nodes are: [0, 1, 1, 2, 2, 2, 3, 3, 3, 4]
The initial binary tree's nodes are replaced with their corresponding depths. The root node value is 0, and as we move down the tree, the depth of the nodes increases. The leaf nodes have the highest depth value, which is 4 in this case.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment