Under which circumstances can a Binary Search Tree and a Partially-Ordered Tree be equivalent?

1
votes

This is my first question over here, and probably not the last.

I'm currently working with different kinds of trees, specially binary search trees, but also some others like AVL or partially-ordered trees.

I've been thinking about the possibility of a binary search tree and a partially-ordered tree being equivalent under some circumstances, but I'm not quite sure if that is actually possible.

Could someone help me?

Thanks!

1
data-structuresbinary-treebinary-search-treerecursive-datastructures
providing details on what you have done and whats not working like it should, normally help get an answer. – Jawad
@Jawad hey! I didn't code anything, it's just theory! – Adrisui3

1 Answers

0
votes

A binary search tree is a binary tree, where every node is greater than any node of its left subtree and less than any node of its right subtree.

A partially ordered tree is a tree, where every node is greater than (or equal to) any of its children.

Apart from the base case of any tree having only one(the root) node,also if a binary search tree happened to be constructed by inserting smaller and smaller elements, for example:

                      20
                     /
                   15
                  /
                 7
                /
               2

and thus resulting in a BST with only left subtrees for all its nodes, then, is also a partially ordered tree, since it also satisfies its invariant.