Skip to main content

Replace node with depth in a binary tree

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
Last updated on by Kalkicode




Comment

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