CODEWITHSUNDEEP
algorithmrecursiontime-complexitybig-ospace-complexity
Salvador Vigo
Salvador Vigo

Reputation: 457

Time and space complexity of recursive random tree structure

I am trying to find a good example to understand the time and the space complexity (in Big O notation) when recursively map a random tree.

I found examples for a binary search tree, but I am not sure if this case will apply to my case.

Let suppose we have a tree of nodes. Each of these nodes can have a random number of child nodes as well.

ParentNode[ChildNode1.1[ChildNode2.1,ChildNode2.2], ChildNode1.2[ChildNode2.3]]

My task consist into copy the ParentNode into a new CopyNode with all the children. For that, my functions is:

CopyNode = getChildNode(ParentNode)

Node getChildNode(Node node){
    Node newNode = node.copy();
    if (node.getChildren().empty()){
        return newNode
    }
    for (Node child: node.getChildren()){
        newNode.addChild(getChildNode(child))
    }
    return newNode;
}

As you can see it is a recursive function that iterates to all branches and nodes in the tree.

I have two questions.

  1. What would be the time and space complexity of the function. I am not sure if it is O(n), since some recursive functions work like that. Or O(XeN) exponential.

  2. Could be an efficient way to implement the function?

Upvotes: 0

Views: 246

Answers (1)

user58697
user58697

Reputation: 7923

node.copy() is called exactly once per each source node. Time complexity is indeed O(N) (N being the number of nodes in a source tree).

Space complexity is proportional to the depth of the source tree. Worst case is again O(N).

Testing for a special case of node.getChildren().empty() is not necessary.

Upvotes: 2

Related Questions