Register to get access to free programming courses with interactive exercises

Definitions JS: Trees

File structures are an example of a tree that everyone who uses a computer is familiar with. It consists of directories and different kinds of files.

nodejs-package # root directory
├── Makefile # file
├── README.md # file
├── __tests__ # directory
│   └── half.test.js # file
├── babel.config.js # file
└── node_modules # directory
    └── @babel # directory
        └── cli # directory
            └── LICENSE # file

It's called a tree because of its structure. All elements in the file system are arranged in a hierarchy. In it, the top level is the root directory (or disk, if we're talking about Windows), and then there are files and directories, which themselves may contain more files and directories.

A vital feature of the tree structure is that it is recursive. In other words, the tree consists of subtrees, which in turn comprised of subtrees, which in turn consist of... This feature is the defining factor of the main ways that developers work with trees, all of which are recursive in one way or another.

Trees consist of nodes и edges between them. Edges don't actually exist, they only help to visualize the connection and, if necessary, describe it. Nodes are divided into two types: internal nodes (those that have child nodes) and leaf nodes (that don't). In the case of a file system, leaf nodes are represented by files and internal nodes by directories.

Each node in the tree has a parent (or ancestor). The only exception is the root node – it has no parents, and that's where the tree begins. In general, any number of descendants of any internal node can exist. In addition, working with trees means that you need to understand the concept of depth. Depth determines how many steps through the nodes from the root you need to reach the current one (the one we are looking at). Nodes that are at the same depth and have a common parent are sibling nodes.

Implementation

The number of tree implementations is endless. The most basic one is nested arrays:

[['index.html', 'main.js'], 'index.js', ['favicon.ico', 'app.css']];
//                    * the root is the array itself
//         /          |         \
//       *         index.js       *
//  /         |               |        \
// index.html main.js   favicon.ico app.css

// A couple more examples of trees with arbitrary data:
[]; // empty tree
[3, 2, [3, 8], [[8], 3]];
[1, null, [[3]], [5, 'string', [undefined, [3], { key: 'value' }]]];

In the examples above, the root is the array itself, and all its elements are children. If the child is not an array, it is treated like a leaf node; otherwise, it's treated like an internal node. The inner node, in turn, consists of children.

Any tree consists of two large parts:

  1. Data that is stored inside the tree
  2. The tree structure, which is responsible for the relationships between the data
[['index.html', 'main.js'], 'index.js', ['favicon.ico', 'app.css']];

What is the structure, and what is the data in this tree? The data here are leaf nodes, and the internal arrays are the structure. They determine where the data (in this case, files) are located but do not contain any data themselves. Organizing a tree in this way is not conducive to a file structure. This tree doesn't even allow you to set a name for the directory.

Let's expand the structure to be able to add more data. Let's represent each element in the tree as an array, where the first element is the value stored in the node, and the second element is an array of the node's children. If the second element is missing, then we are dealing with a leaf.

['app', [ // Root
  ['dist', [ // Internal node
    ['index.html'], // Leaf
    ['main.js'] // Leaf
  ]],
  ['index.js'], // Leaf
  ['assets', [ // Internal node
    ['favicon.ico'], // Leaf
    ['app.css'], // Leaf
  ]],
]];

//                   app
//         /          |         \
//       dist      index.js   assets
//  /         |               |        \
// index.html main.js   favicon.ico app.css

This variant is more verbose, but allows you to store data in any node, even non-leaf. And it doesn't have to be a string, like in the example above. Changing data on objects will allow you to add anything there.

And the most flexible and convenient way to represent trees is through objects: each node is an object, and arrays store only the children list.

// Note the separation of structure and data
// Here it's much more obvious
{
  value: 5,
  children: [
    { value: 10 },
    { value: 100 },
    { value: 'nested', children: [/* ... */] }
  ]
}

By and large, both the array and the object themselves can always represent trees. This is true for any recursive data structure, that is, a structure whose elements can be the structure itself. Any array can contain an array, just as any object can contain an object.


Recommended materials

  1. Fractal
  2. Abstract syntax JavaScript tree

Hexlet Experts

Are there any more questions? Ask them in the Discussion section.

The Hexlet support team or other students will answer you.

About Hexlet learning process

For full access to the course you need a professional subscription.

A professional subscription will give you full access to all Hexlet courses, projects and lifetime access to the theory of lessons learned. You can cancel your subscription at any time.

Get access
130
courses
1000
exercises
2000+
hours of theory
3200
tests

Sign up

Programming courses for beginners and experienced developers. Start training for free

  • 130 courses, 2000+ hours of theory
  • 1000 practical tasks in a browser
  • 360 000 students
By sending this form, you agree to our Personal Policy and Service Conditions

Our graduates work in companies:

<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.bookmate">Bookmate</span>
<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.healthsamurai">Healthsamurai</span>
<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.dualboot">Dualboot</span>
<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.abbyy">Abbyy</span>
Suggested learning programs

From a novice to a developer. Get a job or your money back!

Frontend Developer icon
Profession
beginner
Development of front-end components for web applications
start anytime 10 months

Use Hexlet to the fullest extent!

  • Ask questions about the lesson
  • Test your knowledge in quizzes
  • Practice in your browser
  • Track your progress

Sign up or sign in

By sending this form, you agree to our Personal Policy and Service Conditions

Toto Image

Ask questions if you want to discuss a theory or an exercise. Hexlet Support Team and experienced community members can help find answers and solve a problem.