# Did I invent a new data structure?

I needed to implement a priority queue for a project I'm working on and had this idea. In a priority queue BST implementation wouldn't it be more efficient if the poll node pointed to its parent since it's guaranteed to not have a left child? This would make polling faster since we don't have to traverse the tree to find the poll node's parent and link it with the poll node's right child. for example:

poll():

when we call poll() here it'll go to the poll's parent (5) and make its left child the poll's right child, and then go to the new poll node (4) and make it point to its new parent. this is an O(1) operation.

Worst case is the poll's right child has left children of its own, in which case we'll have to traverse the leftmost node in that subtree and make it point to its parent and assign it as the poll node. Now it becomes O(log(n)) but faster than regular traversal since we're not starting from the root.

add() is similar to a regular BST except for two optimizations.

1. If the new data is lower than the poll node's data then make it the poll node's left child and have it point to its parent (old poll node) and assign the newly added node as the poll node. this is an O(1) operation.
2. If the new data is lower than the poll node's right child's data then insert starting from that subtree. This is an O(log(n)) operation but is faster since we're not starting from the root.

Other than that insert is like a normal BST.

Does this data structure make sense to use in practice?

• en.wikipedia features threaded binary trees. Commented Jul 26, 2022 at 6:47
• "Did i invent a new data structure" No. It still is a binary tree as it stores the elements in that way. Commented Jul 26, 2022 at 6:50
• The answer to your question requires a thorough discussion of the efficiency of the various operations, in front pf practical use cases. All I can say is that such a structure does not seem to be much in use.
– user16034
Commented Jul 26, 2022 at 8:12