Open mateogianolio opened 8 years ago
Getting tree length
(or size
, depth
, whatever you want to call it) in O(1) is possible if you attach a length property to the class and increment it on push
. Otherwise, the general way of getting tree length is:
length(node) {
if (!node)
return 0;
return 1 + this.length(node.left) + this.length(node.right);
}
Getting tree height
:
height(node) {
if (!node)
return 0;
return 1 + Math.max(this.height(node.left), this.height(node.right));
}
In this short post we will use the new class syntax, and generators to create an incredibly light-weight binary tree representation that can easily be extended into e.g. a heap or a binary search tree (BST).
A binary tree node consists of a value and two children, usually referred to as
left
andright
. To make use of classes, we can represent it as follows:Binary tree traversal is usually done with depth-first search. There are three orders of depth-first traversal: pre-order, in-order and post-order.
In-order traversal in ES6 generator land looks something like this:
Implementing pre-order and post-order is simply a matter of moving
yield node.value
before (pre) or after (post) recursion.We now know enough to start implementing our binary tree.
Let's create a BST by extending the
BinaryTree
class with apush
method:Tree traversal with the
for ... of
syntax:We can define a standard iterator (
[Symbol.iterator]
) for theBinaryTree
class to avoid having to call thetraverse()
function:Tree traversal looks like this:
The spread operator can be used to unpack iterables, so the syntax can be further simplified:
Let's finish off by adding a
getter
for thelength
property to ourBinaryTree
class:We can now get the length of the tree: