CODEWITHSUNDEEP
data-structures
Manh Nguyen
Manh Nguyen

Reputation: 69

What is the Big-O complexity of a general tree?

What I mean by general tree is an unbalanced tree with multiple child nodes (not restricted to 2 child node for each branch like Binary Tree). What is the Big-O complexity of remove node, insert node, find node

Upvotes: 1

Views: 3565

Answers (2)

Nick Zuber
Nick Zuber

Reputation: 5637

If you're talking about a regular k-ary tree that does nothing special with its data, then to find any one node in the tree would take O(n) time assuming there are n nodes.

Inserting a node would be O(1) since you can store it wherever you want, and removing a node would be O(n) since you'd have to look at every node (worst case) to find the one to delete, and since there's no order to the data you don't have to do anything with the rest of the nodes.

Upvotes: 1

djmayank
djmayank

Reputation: 392

The average time complexity of searching in balanced BST in O(log(n)). The worst case complexity of searching in unbalanced binary tree is O(n).

Upvotes: 1

Related Questions