Depth first traversal of Binary Trees in Javascript

Eugene Vedensky — Wed, 15 Jul 2020 03:20:42 +0000

Depth First Traversal in Binary Trees

Hello!

In an effort to teach myself fundamentals that I might have missed in my rudimentary yet effective bootcamp experience, I'm going to cover some basics in a series about data structures and algorithms. As you might have surmised, in this post we're going to be discussing depth first traversal

A depth first traversal is a way of accessing every node in graph or binary tree.

A depth first traversal is characterized by the direction of the traversal.

In other words, we traverse through one branch of a tree until we get to a leaf, and then we work our way back to the trunk of the tree.

In this post, I'll show and implement three types of depth first traversal.

Inorder traversal

As 'depth first' implies, we will reach the 'leaf' (a node with no children) by traveling downward in a recursive manner.

Inorder traversal adheres to the following patterns when traveling recursively:

Go to left-subtree
Visit Node
Go to right-subtree

We can illustrate this concept with the follow gif

Let's code!

For the following examples we'll be using the Tree class I've defined below.

class Tree {
  constructor(value, left, right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

Let's go ahead and create the tree we see in the example gif

tree = new Tree(
  1,
  new Tree(2, new Tree(4, new Tree(8)), new Tree(5)),
  new Tree(3, new Tree(6, new Tree(9), new Tree(10)), new Tree(7))
);

Finally, let's implement inorder traversal:

const inOrderTraversal = (node, cb) => {
  if (node !== undefined) {
    inOrderTraversal(node.left, cb);
    cb(node.value);
    inOrderTraversal(node.right, cb);
  }
};

inOrderTraversal(tree, console.log);
// 8, 4, 2, 5, 1, 9, 6, 10, 3, 7

As you can see, the code mimics the steps outlined above.

The trickiest bit of this visualization is imagining the recursion until you hit the left-most leaf. I personally groan at the sight of recursion, but it's just something that has to be confronted with depth first traversal.

Fun fact:

Inorder Traversal of Binary Search Tree will always give you Nodes in sorted manner

Preorder traversal

Preorder traversal adheres to the following patterns when traveling recursively:

Visit Node
Go to left-subtree
Go to right-subtree

In other words, preorder is extremely similar to inorder except for the fact it will visit the root of the node first.

Let's implement preorder traversal:

const preOrderTraversal = (node, cb) => {
  if (node !== undefined) {
    cb(node.value);
    preOrderTraversal(node.left, cb);
    preOrderTraversal(node.right, cb);
  }
};
preOrderTraversal(tree, console.log);
// 1, 2, 4, 8, 5, 3, 6, 9, 10, 7

Postorder traversal

Post traversal adheres to the following patterns when traveling recursively:

Go to left-subtree
Go to right-subtree
Visit Node

Once again, postorder is extremely similar to the others except for the fact it will visit the left subtree, then the right subtree and finally the node itself.

Let's implement postorder traversal:

const postOrderTraversal = (node, cb) => {
  if (node !== undefined) {
    postOrderTraversal(node.left, cb);
    postOrderTraversal(node.right, cb);
    cb(node.value);
  }
};
postOrderTraversal(tree, console.log);
// 8, 4, 5, 2, 9, 10, 6, 7, 3, 1

That wraps it up for depth first traversal...as far as I know. Please let me know if you've learned anything or I've made any egregious mistakes!

Till next time, cheers!

You are not the code you write

Eugene Vedensky — Wed, 13 Mar 2019 02:36:57 +0000

It’s a common sentiment to hear that your value as a human being does not come from the output of your labor.

Our work is a central part of our identity and it’s important to take pride in our professional and sometimes personal accomplishments, but it is my sincere hope that we all have more than our vocation to reply upon when the existential question of our who we are comes sharply into focus.

Like many others in Technology, I don’t have a traditional four year computer science degree; I’m the product of java focused bootcamp so I’ll be the first to admit I feel particularly susceptible to imposter syndrome when comparing my base of knowledge to some of my colleagues’. In addition to this, I tend throw myself into whatever craft or hobby I’m pursuing (currently it’s rock-climbing) so I emphatically understand the desire to become the art you make whatever through whatever medium you choose to express yourself in.

Having said all this, I will still never understand some of my peers who’s entire sense of self relies on being a ‘good coder’. I’ll recount the story of Tyler (named changed), a fellow boot camp student who fought very viciously in the initial four week period of our cohort to establish himself as THE dev guy guru tech dude hobbyist coder genius. The impression he wanted to give was that he was clearly some kind of code wizard— he cast this spell by asking technical questions well outside the scope of most student’s initial knowledge and priding himself on having already done some coding years before as a computer science major.

The problem with Tyler however is that his hard-earned sense of pride was quite fragile and began to rapidly shatter the moment other talented students started picking up some momentum and getting comfortable with the world of programming. I vividly recall Tyler lamenting his perceived fall in ‘rank’ to an exceedingly patient instructor during the course of the program. I must admit, during my time in the boot camp I had very little sympathy for Tyler and his plight; however, after having spent some time in the industry I’ve been able to empathize with Tyler and many others like him, maybe we are all prisoners of our own self imposed aspirations of sometimes unattainable excellence.

Within yourself there are a multitude of infinite identities waiting to be discovered, each one filled with nuance and complexity. Why shove all your value into this one coveted monicker-- why gate your entire sense of worth behind an impossibly limiting expectation of perfection. Realize your idea of an amazing engineer is a moving goal post-- the glimmer of a mirage on an ever shifting horizon. You can close the distance between your skills and your ideas of pinnacle performance, but the approach is inherently asymptotic. There will always be a gap between you and your sense of excellence no matter how infinitesimal. Embrace that distance and join me in saying that good enough is good enough and look forward to the things in your life that aren’t coding. As for myself, I just want to climb some more (literal) walls.

I've no doubt this idea and discussion can be generalized to many professions and ‘curated identities'. Please join me in discussing if you've had similar experiences in your workplace or school.

DEV Community: Eugene Vedensky