underdisplayname
underdisplayname

Reputation: 293

Why an arbitrary binary tree cannot be transformed into a BST only using binary tree rotation?

midterm question

I don't understand why the second statement is false: "An arbitrary binary tree can be transformed into a binary search tree." What are BT examples that cannot be transformed into BST after as many binary tree rotations as needed?

Upvotes: 2

Views: 32

Answers (1)

jess
jess

Reputation: 41

Any non-BST BT cases will do. This is because BST rotation preserves the BST property - smaller elements on the left side and bigger elements on the right side of their root. Likewise, if the BT is not a BST, it preserves its properties too.

Upvotes: 1

Related Questions