A binary 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. Any given node can have at most two children (left and right). The first node in the binary tree is the root, whereas nodes without any children are the leaves.
Each node in a binary tree data structure must have the following properties:
key
: The key of the nodevalue
: The value of the nodeparent
: The parent of the node (null
if there is none)left
: A pointer to the node's left child (null
if there is none)right
: A pointer to the node's right child (null
if there is none)The main operations of a binary tree data structure are:
insert
: Inserts a node as a child of the given parent noderemove
: Removes a node and its children from the binary treefind
: Retrieves a given nodepreOrderTraversal
: Traverses the binary tree by recursively traversing each node followed by its childrenpostOrderTraversal
: Traverses the binary tree by recursively traversing each node's children followed by the nodeinOrderTraversal
: Traverses the binary tree by recursively traversing each node's left child, followed by the node, followed by its right childclass BinaryTreeNode {
constructor(key, value = key, parent = null) {
this.key = key;
this.value = value;
this.parent = parent;
this.left = null;
this.right = null;
}
get isLeaf() {
return this.left === null && this.right === null;
}
get hasChildren() {
return !this.isLeaf;
}
}
class BinaryTree {
constructor(key, value = key) {
this.root = new BinaryTreeNode(key, value);
}
*inOrderTraversal(node = this.root) {
if (node.left) yield* this.inOrderTraversal(node.left);
yield node;
if (node.right) yield* this.inOrderTraversal(node.right);
}
*postOrderTraversal(node = this.root) {
if (node.left) yield* this.postOrderTraversal(node.left);
if (node.right) yield* this.postOrderTraversal(node.right);
yield node;
}
*preOrderTraversal(node = this.root) {
yield node;
if (node.left) yield* this.preOrderTraversal(node.left);
if (node.right) yield* this.preOrderTraversal(node.right);
}
insert(
parentNodeKey,
key,
value = key,
{ left, right } = { left: true, right: true }
) {
for (let node of this.preOrderTraversal()) {
if (node.key === parentNodeKey) {
const canInsertLeft = left && node.left === null;
const canInsertRight = right && node.right === null;
if (!canInsertLeft && !canInsertRight) return false;
if (canInsertLeft) {
node.left = new BinaryTreeNode(key, value, node);
return true;
}
if (canInsertRight) {
node.right = new BinaryTreeNode(key, value, node);
return true;
}
}
}
return false;
}
remove(key) {
for (let node of this.preOrderTraversal()) {
if (node.left.key === key) {
node.left = null;
return true;
}
if (node.right.key === key) {
node.right = null;
return true;
}
}
return false;
}
find(key) {
for (let node of this.preOrderTraversal()) {
if (node.key === key) return node;
}
return undefined;
}
}
class
for the BinaryTreeNode
with a constructor
that initializes the appropriate key
, value
, parent
, left
and right
properties.isLeaf
getter, that uses Array.prototype.length
to check if both left
and right
are empty.hasChildren
getter, that is the reverse of the isLeaf
getter.class
for the BinaryTree
with a constructor
that initializes the root
of the binary tree.preOrderTraversal()
generator method that traverses the binary tree in pre-order, using the yield*
syntax to recursively delegate traversal to itself.postOrderTraversal()
generator method that traverses the binary tree in post-order, using the yield*
syntax to recursively delegate traversal to itself.inOrderTraversal()
generator method that traverses the binary tree in in-order, using the yield*
syntax to recursively delegate traversal to itself.insert()
method, that uses the preOrderTraversal()
method to find the given parent node and insert a new child BinaryTreeNode
either as the left
or right
child, depending on the passed options object.remove()
method, that uses the preOrderTraversal()
method and Array.prototype.filter()
to remove a BinaryTreeNode
from the binary tree.find()
method, that uses the preOrderTraversal()
method to retrieve the given node in the binary tree.const tree = new BinaryTree(1, 'AB');
tree.insert(1, 11, 'AC');
tree.insert(1, 12, 'BC');
tree.insert(12, 121, 'BG', { right: true });
[...tree.preOrderTraversal()].map(x => x.value);
// ['AB', 'AC', 'BC', 'BCG']
[...tree.inOrderTraversal()].map(x => x.value);
// ['AC', 'AB', 'BC', 'BG']
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.find(12).left; // null
tree.find(12).right.value; // 'BG'
tree.remove(12);
[...tree.postOrderTraversal()].map(x => x.value);
// ['AC', 'AB']
Would you like to help us improve 30 seconds of code?Take a quick survey
Snippet collection
A guide to some of the most commonly-used data structures, along with JavaScript implementations and examples.
JavaScript, Object
A binary search tree is a data structure consisting of a set of ordered linked nodes representing a hierarchical tree structure, in which each node can have at most two children.
JavaScript, Object
A tree is a data structure consisting of a set of linked nodes representing a hierarchical tree structure.
JavaScript, Object
A doubly linked list is a linear data structure where each element points both to the next and the previous one.