My Docs
BlogGithubLinkedin
Cheat Sheets
Cheat Sheets
  • πŸ“‹Cheat Sheets
    • Files
    • Terminal Cheat Sheet
    • Flexbox Cheat Sheet
    • Common HTTP status codes Cheat Sheet
    • networking_cheatsheet
    • Regular Expressions Cheat Sheet
    • REGEX units Cheat Sheet
  • bash_cheatsheet
  • Google dork cheatsheet
  • Cheatsheet-v2
  • πŸ•ΈοΈπŸ’» πŸ’» Javascript
    • JavaScript
      • Javascript Python cheatsheet
      • General
        • JavaScript Promise API Cheat Sheet
        • Chai.js
        • Canvas
        • ES6 EXPORTS
        • Asynchronous JavaScript Cheat Sheet
      • React
        • React Cheat Sheet
          • React Component Guide
        • React Patterns:
        • react-examples
        • React.js
          • Bootstrap
        • React.js cheatsheet 2
        • React-router
        • React.js (v0.14)
        • React.js
        • React Patterns:
      • βš–οΈLibraries & Frameworks
        • LOADASH Cheat Sheet
        • sequelize_cheatsheet
        • Sequelize Cheatsheet
      • Node & Express
        • ExpressJS Cheat Sheet
      • CHEATSHEET
      • NPM Cheat Sheet
        • NPM Command Line Cheat Sheet
      • Function Context Cheatsheet
      • js-model
  • πŸ’»CS-Concepts
    • Computer Science Concepts
      • Data Structures
        • The Queue data structure
        • Cheat Sheet for Beginners: JavaScript Data Structures Methods
        • MDN Web Docs Glossary: Definitions of Web-related terms \| MDN
        • Data Structures Cheat Sheet
        • The Tree data structure
        • An Executable Data Structures Cheat Sheet for Interviews
      • networking_cheatsheet
  • Tools
    • πŸ› οΈTools
      • VSCODE Cheat Sheet
      • Emmet
  • πŸ“ΌGuides-Tutorials
    • Tutorials
      • React.js
  • JavaScript Arrays
  • editorconfig
  • AWS CLI
  • ES6 EXPORTS
  • Flynn
  • Github
    • Github
      • Github Cheat Sheet
    • git log
    • GITHUB Cheat Sheet
      • An Executable Data Structures Cheat Sheet for Interviews
      • graphs_cheatsheet
  • General
    • General
  • πŸ‘¨β€πŸ’»πŸ‘¨πŸ’» πŸ‘¨πŸ’» πŸ’» Programming Languages
    • 🐍Python:
      • Python
        • What is Python
      • Regex In Python
    • HTML
  • EC2 API tools
    • MARKDOWN
    • πŸ§˜β™‚ PSQL
      • POSTGRES
      • postgreSQL_cheatsheet
  • ES6 IMPORTS
    • bash_cheatsheet
    • cleancode
    • πŸ”¨Bash
      • Bash Cheat Sheet
      • Learn Bash Scripting: Bash Scripting Cheatsheet
      • Curl
      • Bash Shortcuts Cheat Sheet
      • SSH Cheatsheet
      • Linux
    • CSS
      • CSS
        • CSS Grid
        • cssnext
        • CSS Cheat Sheet
        • CSS Flex Box
        • CSS tricks
        • CSS selectors
        • cssnext
        • CSS background
        • CSS animations
    • Typescript
  • Computer Science Concepts
    • An Executable Data Structures Cheat Sheet for Interviews
    • graphs_cheatsheet
    • networking_cheatsheet
    • Firebase
    • networking_cheatsheet
    • πŸ›Heroku Cheat Sheet
    • Binary Tree
  • πŸ“šDocs
    • Docs
      • editorconfig
      • EC2 API tools
      • Asynchronous JavaScript Cheat Sheet
      • CHEATSHEET (3)
      • js-model
      • Emmet
      • Binary Tree
      • Python
      • Contributor Covenant Code of Conduct
      • networking_cheatsheet
      • Common HTTP status codes Cheat Sheet
      • AWS CLI
      • Linux
      • networking_cheatsheet
      • React Patterns:
      • MDN Web Docs Glossary: Definitions of Web-related terms \| MDN
      • JavaScript Arrays
      • Linux
      • Javascript Python cheatsheet
      • Cheatsheet-v2
      • Binary Tree
      • Heroku Cheat Sheet
      • Asynchronous JavaScript Cheat Sheet
      • Cheatsheet Compilation
      • AWS CLI
      • EC2 API tools
      • Common HTTP status codes Cheat Sheet
      • Firebase
      • The Queue data structure
      • Cheat Sheet for Beginners: JavaScript Data Structures Methods
Powered by GitBook
On this page
  • Get the code on Github
  • Definition
  • Complexity
  • The code

Was this helpful?

Edit on GitHub
  1. CS-Concepts
  2. Computer Science Concepts
  3. Data Structures

The Tree data structure

PreviousData Structures Cheat SheetNextAn Executable Data Structures Cheat Sheet for Interviews

Last updated 3 years ago

Was this helpful?

The #data-structures series is a collection of posts about reimplemented data structures in JavaScript.

Get the code on Github

Of course, all the code can also be found on Github in the repository .

Definition

A Tree is a widely used data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node. A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root node. From

Complexity

Average

Access

Search

Insertion

Deletion

O(n)

O(n)

O(n)

O(n)

To get a full overview of the time and space complexity of the Tree data structure, have a look to this excellent .

The code

function Node(data) {
  this.data = data;
  this.children = [];
}

function Tree() {
  this.root = null;
}

Tree.prototype.add = function(data, toNodeData) {
  var node = new Node(data);
  var parent = toNodeData ? this.findBFS(toNodeData) : null;
  if(parent) {
    parent.children.push(node);
  } else {
    if(!this.root) {
      this.root = node;
    } else {
      return 'Root node is already assigned';
    }
  }
};
Tree.prototype.remove = function(data) {
  if(this.root.data === data) {
    this.root = null;
  }

  var queue = [this.root];
  while(queue.length) {
    var node = queue.shift();
    for(var i = 0; i < node.children.length; i++) {
      if(node.children[i].data === data) {
        node.children.splice(i, 1);
      } else {
        queue.push(node.children[i]);
      }
    }
  }
};
Tree.prototype.contains = function(data) {
  return this.findBFS(data) ? true : false;
};
Tree.prototype.findBFS = function(data) {
  var queue = [this.root];
  while(queue.length) {
    var node = queue.shift();
    if(node.data === data) {
      return node;
    }
    for(var i = 0; i < node.children.length; i++) {
      queue.push(node.children[i]);
    }
  }
  return null;
};
Tree.prototype._preOrder = function(node, fn) {
  if(node) {
    if(fn) {
      fn(node);
    }
    for(var i = 0; i < node.children.length; i++) {
      this._preOrder(node.children[i], fn);
    }
  }
};
Tree.prototype._postOrder = function(node, fn) {
  if(node) {
    for(var i = 0; i < node.children.length; i++) {
      this._postOrder(node.children[i], fn);
    }
    if(fn) {
      fn(node);
    }
  }
};
Tree.prototype.traverseDFS = function(fn, method) {
  var current = this.root;
  if(method) {
    this['_' + method](current, fn);
  } else {
    this._preOrder(current, fn);
  }
};
Tree.prototype.traverseBFS = function(fn) {
  var queue = [this.root];
  while(queue.length) {
    var node = queue.shift();
    if(fn) {
      fn(node);
    }
    for(var i = 0; i < node.children.length; i++) {
      queue.push(node.children[i]);
    }
  }
};
Tree.prototype.print = function() {
  if(!this.root) {
    return console.log('No root node found');
  }
  var newline = new Node('|');
  var queue = [this.root, newline];
  var string = '';
  while(queue.length) {
    var node = queue.shift();
    string += node.data.toString() + ' ';
    if(node === newline && queue.length) {
      queue.push(newline);
    }
    for(var i = 0; i < node.children.length; i++) {
      queue.push(node.children[i]);
    }
  }
  console.log(string.slice(0, -2).trim());
};
Tree.prototype.printByLevel = function() {
  if(!this.root) {
    return console.log('No root node found');
  }
  var newline = new Node('\n');
  var queue = [this.root, newline];
  var string = '';
  while(queue.length) {
    var node = queue.shift();
    string += node.data.toString() + (node.data !== '\n' ? ' ' : '');
    if(node === newline && queue.length) {
      queue.push(newline);
    }
    for(var i = 0; i < node.children.length; i++) {
      queue.push(node.children[i]);
    }
  }
  console.log(string.trim());
};

var tree = new Tree();
tree.add('ceo');
tree.add('cto', 'ceo');
tree.add('dev1', 'cto');
tree.add('dev2', 'cto');
tree.add('dev3', 'cto');
tree.add('cfo', 'ceo');
tree.add('accountant', 'cfo');
tree.add('cmo', 'ceo');
tree.print(); // => ceo | cto cfo cmo | dev1 dev2 dev3 accountant
tree.printByLevel();  // => ceo \n cto cfo cmo \n dev1 dev2 dev3 accountant
console.log('tree contains dev1 is true:', tree.contains('dev1')); // => true
console.log('tree contains dev4 is false:', tree.contains('dev4')); // => false
console.log('--- BFS');
tree.traverseBFS(function(node) { console.log(node.data); }); // => ceo cto cfo cmo dev1 dev2 dev3 accountant
console.log('--- DFS preOrder');
tree.traverseDFS(function(node) { console.log(node.data); }, 'preOrder'); // => ceo cto dev1 dev2 dev3 cfo accountant cmo
console.log('--- DFS postOrder');
tree.traverseDFS(function(node) { console.log(node.data); }, 'postOrder'); // => dev1 dev2 dev3 cto accountant cfo cmo ceo
tree.remove('cmo');
tree.print(); // => ceo | cto cfo | dev1 dev2 dev3 accountant
tree.remove('cfo');
tree.print(); // => ceo | cto | dev1 dev2 dev3



πŸ’»
data-structures-in-javascript
Wikipedia
Big O cheat sheet
Source