javascript/algorithms/data-structures/BinaryTree.js at master · AllAlgorithms/javascript · GitHub

This repository was archived by the owner on Sep 7, 2025. It is now read-only.

History

138 lines (125 loc) · 3.66 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

class Node {

constructor(value) {

this.value = value;

this.left = null;

this.right = null;

}

class BinarySearchTree {

constructor() {

this.root = null;

}

insert(value) {

var newNode = new Node(value);

if (this.root === null) {

this.root = newNode;

return this;

}

var current = this.root;

while (true) {

if (value === current.value) return undefined;

if (value < current.value) {

if (current.left === null) {

current.left = newNode;

return this;

}

current = current.left;

} else {

if (current.right === null) {

current.right = newNode;

return this;

}

current = current.right;

}

find(value) {

if (this.root === null) return false;

var current = this.root,

found = false;

while (current && !found) {

if (value < current.value) {

current = current.left;

} else if (value > current.value) {

current = current.right;

} else {

found = true;

}

if (!found) return undefined;

return current;

}

contains(value) {

if (this.root === null) return false;

var current = this.root,

found = false;

while (current && !found) {

if (value < current.value) current = current.left;

else if (value > current.value) current = current.right;

else return true;

}

return false;

}

BreadthFirstSearch() {

let node = this.root,

data = [],

queue = [];

queue.push(node);

while (queue.length) {

node = queue.shift();

data.push(node.value);

if (node.left) queue.push(node.left);

if (node.right) queue.push(node.right);

}

return data;

}

DepthFirstSearchPreOrder() {

let data = [];

function traverse(node) {

data.push(node.value);

if (node.left) traverse(node.left);

if (node.right) traverse(node.right);

}

traverse(this.root);

return data;

}

DepthFirstSearchPostOrder() {

let data = [];

function traverse(node) {

if (node.left) traverse(node.left);

if (node.right) traverse(node.right);

data.push(node.value);

}

traverse(this.root);

return data;

}

DepthFirstSearchInOrder() {

let data = [];

function traverse(node) {

if (node.left) traverse(node.left);

data.push(node.value);

if (node.right) traverse(node.right);

}

traverse(this.root);

return data;

}

// 10

// 5 13

// 2 7 11 16

var tree = new BinarySearchTree();

tree.insert(10);

tree.insert(5);

tree.insert(13);

tree.insert(11);

tree.insert(2);

tree.insert(16);

tree.insert(7);

console.log("node with value 13:", tree.find(13));

console.log("node with value 19:", tree.find(19));

console.log("tree coontais node with value 2:", tree.contains(2));

console.log("tree coontais node with value 534:", tree.contains(534));

console.log("BreadthFirstSearch:", tree.BreadthFirstSearch());

console.log("DepthFirstSearchPreOrder:", tree.DepthFirstSearchPreOrder());

console.log("DepthFirstSearchPostOrder:", tree.DepthFirstSearchPostOrder());

console.log("DepthFirstSearchInOrder:", tree.DepthFirstSearchInOrder());

javascript/algorithms/data-structures/BinaryTree.js at master · AllAlgorithms/javascript · GitHub

Uh oh!

Expand file tree

Breadcrumbs

BinaryTree.js

Latest commit

History

Breadcrumbs

BinaryTree.js

File metadata and controls