Tree Problem

// 0
// ├── 100
// │   ├── 150
// │   │   ├── 200
// │   ├── 250
// ├── 500

$categories = [
	'id' => 0,
	'children' => [
		[
			'id' => 100,
			'children' => [
				[
					'id' => 150,
					'children' => [
						[
							'id' => 200,
							'children' => [],
						],
					],
				],
				[
					'id' => 250,
					'children' => [],
				],
			],
		],
		[
			'id' => 500,
			'children' => [],
		],
	],

];

$givenCategories = [
	500,
	100,
	200,
	600,
];

Έχουμε δύο μεταβλητές $categories και $givenCategories.
Η $categories αναπαριστά τη διάρθρωση των κατηγοριών των προϊόντων ενός καταστήματος (tree structure) και η $givenCategories τις κατηγορίες στις οποίες ανήκει ένα προϊόν.

---

Ζητούμενα

---

• Πρέπει να δημιουργηθεί ένας μονοδιάστατος πίνακας $allAncestors, ο οποίος έχει τόσες θέσεις, όσα είναι και τα paths (διαδρομές) που πληρούν την προϋποθεση να ξεκινάνε από ένα node κάτω από το γονικό node ($id => 0) και καταλήγουν σε ένα leaf (φύλλο).
• Κάθε θέση του παραπάνω πίνακα είναι ένας μονοδιάστατος πίνακας που περιέχει τα nodes του path σε κάθε κλειδί του. Η αναφορά στο root πρέπει να παραλείπεται: πχ [100, 150, 200] και όχι [0, 100, 150, 200]

---

Προϋποθέσεις

---

• Η προσπέλαση του δέντρου πρέπει να γίνει με αναδρομική συνάρτηση.
• Επειδή η αναζήτηση σε δέντρο είναι κοστοβόρα, πρέπει να γίνουν μόνο οι πολύ απαραίτητες αναζητήσεις. Η προσέγγιση αυτού του προβλήματος [της βελτιστοποίσης] δίνεται αναλυτικά στην τελευταία παράγραφο: Αποτέλεσμα

---

Επεξηγήσεις

---

• Κάθε διαδρομή είναι βέβαιο ότι τα id που την αποτελούν είναι πάντοτε μικρότερα των id των αμέσως επόμενων διαδρομών.
• Οι κατηγορίες του προϊόντος είναι έγκυρες ΜΟΝΟ εάν είναι φύλλα του δέντρου (βλ. και Ζητούμενο #1) και δεν είναι απαραίτητο να έχουν δοθεί όλες.

---

Αποτέλεσμα

---

• Ο κώδικας είναι έγκυρος όταν κάνοντας print της $allAncestors έχει ως αποτέλεσμα τον παρακάτω πίνακα:

Array
(
    [0] => Array
        (
            [0] => 500
        )

    [1] => Array
        (
            [0] => 100
            [1] => 150
            [2] => 200
        )

)

• και η προσπέλαση του πίνακα $categories αναφορικά με την αναδρομική αναζήτηση να γίνει ΜΟΝΟ 3 φορές.

---

Σημείωση

---

Αν θεωρείς ότι κάτι πρέπει να λυθεί με άλλον τρόπο, να το κάνεις και να δικαιολογήσεις την προσέγγισή σου