Clone a given binary tree
The problem addressed clone of a given binary tree. A binary tree is a hierarchical data structure composed of nodes where each node has at most two children, referred to as the left child and the right child. Cloning a binary tree means creating a new tree with the same structure and values as the original tree, but the two trees should not share any memory locations. This is useful in various scenarios, such as preserving the original tree's state for future comparisons or modifications.
Problem Statement and Description
Given a binary tree, the goal is to create a clone of that tree, preserving its structure and values. Cloning should be done such that the original and cloned trees are separate entities. The challenge here is to traverse the original tree and create a corresponding clone of each node while maintaining the parentchild relationships.
Example
Consider the following binary tree:
5
/ \
4 7
/ / \
3 6 10
\ /
9 8
The goal is to create a clone of this tree.
Idea to Solve
To solve this problem, your code employs a recursive approach. It traverses the original tree using a preorder traversal (rootleftright) and constructs a clone of each node while mirroring the structure of the original tree.
Pseudocode
Here's a highlevel pseudocode representation of the algorithm:
class TreeNode
properties: data, left, right
class BinaryTree
properties: root
function preorder(node)
if node is not null
create new node called "point" with the same data as "node"
point.left = preorder(node.left)
point.right = preorder(node.right)
return point
return null
function cloneTree
create a new BinaryTree called "tree"
tree.root = preorder(this.root)
return tree
function main
create a new BinaryTree called "tree1"
// Construct tree1 here
create a new BinaryTree called "tree2"
tree2 = tree1.cloneTree()
// Modify tree2 if needed
// Display both trees
Algorithm Explanation
The algorithm starts by defining the TreeNode
and BinaryTree
classes. The
preorder
function is used to traverse the original tree in a preorder manner. At each step, a new node
is created with the same data as the current node, and the function recursively constructs the left and right
subtrees of the clone.
The cloneTree
function initializes a new binary tree, clones the nodes of the original tree using the
preorder
function, and returns the new tree.
Code Solution

1) Clone a binary tree java
2) Deep copy binary tree c++
3) Clone a binary tree in c
4) Clone a binary tree in c#
5) Clone a binary tree in php
6) Clone a binary tree python
7) Clone a binary tree in ruby
8) Clone a binary tree in scala
9) Clone a binary tree in swift
10) Clone a binary tree in kotlin
11) Clone a binary tree in vb.net
12) Clone a binary tree in typescript
13) Clone a binary tree in golang
14) Clone a binary tree in node js
Resultant Output Explanation
The output of your program demonstrates the preorder traversal of both the original and cloned trees. Initially,
the output shows that both trees are identical. However, when you modify the data of the root node in the cloned
tree (tree2.root.data = 99
), you can observe that the original tree remains unaffected, confirming that
the cloning process worked as intended.
Time Complexity
The time complexity of the cloning algorithm is O(n), where n is the number of nodes in the binary tree. This is because each node is visited exactly once during the traversal, and constanttime operations are performed for each node.
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