Skip to main content

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

  1. We start with a recursive function ReplaceNodeWithDepth, which takes two parameters: node (the current node to process) and depth (the depth of the current node).
  2. If the node is NULL, we have reached a leaf node or an empty subtree, so we return from the current call.
  3. Otherwise, we update the node's data with the current depth value.
  4. Then, we make recursive calls to ReplaceNodeWithDepth for the left and right subtrees with an incremented depth value (depth + 1).
  5. 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.

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