# JavaScript Data Structures - Tree

JavaScript, Class · Aug 22, 2021

### Definition

A tree is a data structure consisting of a set of linked nodes that represent a hierarchical tree structure. Each node is linked to others via parent-children relationship. The first node in the tree is the root, whereas nodes without any children are the leaves.

Each node in a tree data structure must have the following properties:

`key`

: The key of the node`value`

: The value of the node`parent`

: The parent of the node (`null`

if there is none)`children`

: An array of pointers to the node's children

The main operations of a tree data structure are:

`insert`

: Inserts a node as a child of the given parent node`remove`

: Removes a node and its children from the tree`find`

: Retrieves a given node`preOrderTraversal`

: Traverses the tree by recursively traversing each node followed by its children`postOrderTraversal`

: Traverses the tree by recursively traversing each node's children followed by the node

### Implementation

```
class TreeNode {
constructor(key, value = key, parent = null) {
this.key = key;
this.value = value;
this.parent = parent;
this.children = [];
}
get isLeaf() {
return this.children.length === 0;
}
get hasChildren() {
return !this.isLeaf;
}
}
class Tree {
constructor(key, value = key) {
this.root = new TreeNode(key, value);
}
*preOrderTraversal(node = this.root) {
yield node;
if (node.children.length) {
for (let child of node.children) {
yield* this.preOrderTraversal(child);
}
}
}
*postOrderTraversal(node = this.root) {
if (node.children.length) {
for (let child of node.children) {
yield* this.postOrderTraversal(child);
}
}
yield node;
}
insert(parentNodeKey, key, value = key) {
for (let node of this.preOrderTraversal()) {
if (node.key === parentNodeKey) {
node.children.push(new TreeNode(key, value, node));
return true;
}
}
return false;
}
remove(key) {
for (let node of this.preOrderTraversal()) {
const filtered = node.children.filter(c => c.key !== key);
if (filtered.length !== node.children.length) {
node.children = filtered;
return true;
}
}
return false;
}
find(key) {
for (let node of this.preOrderTraversal()) {
if (node.key === key) return node;
}
return undefined;
}
}
```

- Create a
`class`

for the`TreeNode`

with a`constructor`

that initializes the appropriate`key`

,`value`

,`parent`

and`children`

properties. - Define an
`isLeaf`

getter, that uses`Array.prototype.length`

to check if`children`

is empty. - Define a
`hasChildren`

getter, that is the reverse of the`isLeaf`

getter. - Create a
`class`

for the`Tree`

with a`constructor`

that initializes the`root`

of the tree. - Define a
`preOrderTraversal()`

generator method that traverses the tree in pre-order, using the`yield*`

syntax to recursively delegate traversal to itself. - Define a
`postOrderTraversal()`

generator method that traverses the tree in post-order, using the`yield*`

syntax to recursively delegate traversal to itself. - Define an
`insert()`

method, that uses the`preOrderTraversal()`

method and`Array.prototype.push()`

to add a new`TreeNode`

to the tree. - Define a
`remove()`

method, that uses the`preOrderTraversal()`

method and`Array.prototype.filter()`

to remove a`TreeNode`

from the tree. - Define a
`find()`

method, that uses the`preOrderTraversal()`

method to retrieve the given node in the tree.

```
const tree = new Tree(1, 'AB');
tree.insert(1, 11, 'AC');
tree.insert(1, 12, 'BC');
tree.insert(12, 121, 'BG');
[...tree.preOrderTraversal()].map(x => x.value);
// ['AB', 'AC', 'BC', 'BCG']
tree.root.value; // 'AB'
tree.root.hasChildren; // true
tree.find(12).isLeaf; // false
tree.find(121).isLeaf; // true
tree.find(121).parent.value; // 'BC'
tree.remove(12);
[...tree.postOrderTraversal()].map(x => x.value);
// ['AC', 'AB']
```

### Written by Angelos Chalaris

I'm Angelos Chalaris, a JavaScript software engineer, based in Athens, Greece. The best snippets from my coding adventures are published here to help others learn to code.

If you want to keep in touch, follow me on GitHub.