CODEWITHSUNDEEP
data-structurestime-complexitybinary-treebig-oclone
guy
guy

Reputation: 31

Time complexity of cloning a binary tree

i am wondering if this code that clones binary tree is in time complexity O(n)? if its O(n) can you explain why? if not, can you suggest a way to do it in time complexity O(n)? 

public TreeNode cloneTree(TreeNode root) {
    if (root == null) return null;
    TreeNode newNode = new TreeNode(root.val);
    newNode.left = cloneTree(root.left);
    newNode.right = cloneTree(root.right);
    return newNode;
}

Upvotes: 2

Views: 840

Answers (1)

ggorlen
ggorlen

Reputation: 56965

You might think it's O(2n) because of the two recursive child calls, but all tree walking algorithms like this are O(n). Every node of the tree is visited only one time; if you add 10 nodes to the tree, you get 10 more stack frames spawned by the algorithm, which is a linear relationship. Yes, the frame has pre-, in- and post- stages to the child visits, so control does return back to the frame multiple times, but this is normal linear behavior and there's no way to improve the complexity while visiting each node in the tree.

Upvotes: 2

Related Questions