What will be the correct sequence of insertion for the following k-d tree?

Category: QuestionsWhat will be the correct sequence of insertion for the following k-d tree?
Editor">Editor Staff asked 1 month ago

What will be the correct sequence of insertion for the following k-d tree?
 
(a) (30,40),(5,25),(70,70),(10,12),(50,30),(35,45)
 
(b) (40,30),(5,25),(12,10),(70,70),(30,50),(45,35)
 
(c) (30,40),(5,25),(10,12),(70,70),(50,30),(35,45)
 
(d) (40,30),(25,5),(12,10),(70,70),(50,30),(45,35)
 
My doubt stems from Trees in section Trees of Data Structures & Algorithms I
 
I got this question during an online exam.

1 Answers
Editor">Editor Staff answered 1 month ago

Right answer is (c) (30,40),(5,25),(10,12),(70,70),(50,30),(35,45)
 
Explanation: The correct sequence of insertion of the above given tree is (30,40),(5,25),(10,12),(70,70),(50,30),(35,45). The insertion is given by, first left, then right.