- Read the "Challenge description" below.
- Make changes to the challenge.js file.
- Commit your changes.
- Wait for the result of the "GitHub Classroom Workflow" action. If it is green - congratulations, you solved this challenge! If not - try again!
- You can watch an example of how to solve a challenge in the video linked in the theoretical lesson preceding this challenge.
The previous challenge showed how to store a Tree in an Array. But how do you convert a Tree from an Array to the more-standard Node form?
To implement a Tree, we'll create a Node class. It will store an integer of Data, and point to 2 child Nodes.
class Node {
constructor(data) {
this.data = data
this.left = null
this.right = null
}
}
- Create a Node
node
from a given celli
in the array:Node node = new Node(array[i])
; - Create the children Nodes from their positions in the array. (See step #1).
- Assign the children Nodes to
node.left
andnode.right
.
You first create a Node, and then you create children Nodes in the same manner. This sounds like a recursive function will be needed!
As mentioned, since trees are recursive structures, recursive functions are used to navigate them.
Here's the above algorithm:
function arrayToTree(array, i) {
if (i >= array.length || array[i] === 0) {
return null
}
const node = new Node(array[i])
node.left = arrayToTree(array, 2*i+1)
node.right = arrayToTree(array, 2*i+2)
return node
}
Pre-order traversal means you process a Node and then process its sub-trees.
Here is the pre-order algorithm:
function preOrder(node) {
if (node === null) {
return '';
}
return `${node.data} ${preOrder(node.left)} ${preOrder(node.right)}`
}
You will be given an array as input, which represents a Tree. Process the array into a Tree of Nodes, as shown above. Then go through the tree and print it in post-order. Print each number space-separated.
const = tree = arrayToTree([10, 1, 2, 3, 4, 5, 6])
console.log(postOrder(tree))
//=> 3 4 1 5 6 2 10
If you cannot see any auto-grading workflows on the Actions page, learn how to fix it in this repo.