CODEWITHSUNDEEP
data-structuresbinary-treetime-complexitybinary-search-treeinorder
Siva R
Siva R

Reputation: 447

Insertion in Threaded Binary leads leads to O(n) time complexity?

Threaded binary tree is effective since it doesn't require any recursion or stack to traverse. My doubt is it makes every insertion takes O(n) (where n is number of nodes in the tree) since for every node we insert it has to be threaded again, isn't it? If I'm right then threaded binary trees are practically ineffective, isn't it?

Upvotes: 0

Views: 2141

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 133975

As the Wikipedia article says:

"A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node."

The key here is "that would normally be null."

Typically, you either include additional fields for the thread links, or you use a bit flag to determine whether the left and right nodes are children or inorder successor/predecessor.

Because the interior node pointers are still the traditional left/right binary tree node references, you can use the standard recursive search to find an insertion spot in O(log n) time.

Upvotes: 1

Related Questions