Posted on by Kalkicode
Code Binary Tree

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.

Clone a binary tree

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 parent-child 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 pre-order traversal (root-left-right) and constructs a clone of each node while mirroring the structure of the original tree.

Pseudocode

Here's a high-level 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 pre-order 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

Resultant Output Explanation

The output of your program demonstrates the pre-order 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 constant-time operations are performed for each node.

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