Time complexity of cloning a binary tree

Question

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;
}

Does this answer your question? [Complexities of binary tree traversals](https://stackoverflow.com/questions/4547012/complexities-of-binary-tree-traversals) — ggorlen, May 08 '20 at 14:37

score 2 · Answer 1 · answered May 08 '20 at 14:36

You might think it's O(2ⁿ) 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.

Time complexity of cloning a binary tree

1 Answers1

Linked