Is the below tree representation of 50,100,400,300,280 correct way to represent cartesian tree?

+1 vote
Is the below tree representation of 50,100,400,300,280 correct way to represent cartesian tree?

(a) true

(b) false

Query is from Cartesian Tree topic in section Binary Trees of Data Structures & Algorithms I

This question was posed to me in class test.

1 Answer

+1 vote
by (789k points)
selected by

Best answer
The correct choice is (a) true

The best I can explain: A tree with heap property (parent is either small or big than children) and when traversed in inorder yields the given input sequence is called as a cartesian tree. as the above figure satisies both the properties. note that even min heap tree can be generated. the above is a max heap tree.

+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+2 votes
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer