Register to get access to free programming courses with interactive exercises

Tree traversal JS: Trees

A step-by-step search of tree elements by connections between ancestor nodes and descendant nodes is called tree traversal. It's assumed that each node will only be visited once during the traversal. Basically, it's the same as traversing any collection using a loop or recursion. Only for trees, there are more ways around than just left to right and right to left.

This course will look at depth-first traversal, the natural way to traverse a tree by depth. You can read about the other methods on Wikipedia or in recommended books from our list.

This is just one way to traverse a tree (or a graph in the general case). The strategy here is to go as deep into one subtree as possible; this algorithm is naturally based on a recursive solution and works itself out.

Depth-first Search

Let's look at this algorithm using the following tree as an example.

//     * A
//   / | \
// B * C * D
//  /|   |\
// E F   G J

Each non-leaf node is marked with an asterisk. The traversal begins at the root node.

  1. Check if node A has children. If true, run a recursive traversal for each child independently
  2. The next subtree is inside the first recursive call:
// B *
//  /|
// E F

Repeat the logic of the first step. We fall to a lower level.

  1. Inside we find leaf node E. The function makes sure that the node has no children, does the necessary work, and returns the result to the top
  2. Again we find ourselves in a situation:
// B *
//  /|
// E F

At this point, as we remember, a recursive call was run on each child. Since the first child has already been visited, the second recursive call goes to node F and does its work there. Then it goes up one, and repeats until it reaches the root.

const tree = mkdir('/', [
  mkdir('etc', [
    mkfile('bashrc'),
    mkfile('consul.cfg'),
  ]),
  mkfile('hexletrc'),
  mkdir('bin', [
    mkfile('ls'),
    mkfile('cat'),
  ]),
]);

const dfs = (tree) => {
  // Print the contents of the node
  console.log(getName(tree));
  // If it is a file, we return control
  if (isFile(tree)) {
    return;
  }

  // Getting the children
  const children = getChildren(tree);

  // Apply the dfs function to all children
  // Many recursive calls within a single function call
  // is called tree recursion
  children.forEach(dfs);
};

dfs(tree);
// => /
// => etc
// => bashrc
// => consul.cfg
// => hexletrc
// => bin
// => ls
// => cat

The logging in the example above is just a demonstration. In reality, we're interested in either changing the tree or aggregating data on it. We'll look at data aggregation later, but now let's look at the change.

Suppose we want to implement a function that changes the owner for the whole tree, i.e., all directories and files. To do this, we have to combine two things: the recursion, which we looked at above, and the node updating we learned in the last lesson.

const changeOwner = (tree, owner) => {
  const name = getName(tree);
  const newMeta = _.cloneDeep(getMeta(tree));
  newMeta.owner = owner;

  if (isFile(tree)) {
    // Return the updated file
    return mkfile(name, newMeta);
  }

  const children = getChildren(tree);
  // Key line
  // Recursive call on each child
  const newChildren = children.map((child) => changeOwner(child, owner));
  const newTree = mkdir(name, newChildren, newMeta);

  // Return the updated directory
  return newTree;
};

// This function can be generalized as a map that works with trees

The key difference from the first example is that instead of printing, new nodes are formed and returned outside. Eventually, a new tree is built from them.

Everything we do in this course will invariably be based on this algorithm. Try opening an editor on your computer and implementing this function yourself without peeking. That way you make sure you understand what's going on.


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.