Hello There. We’re back again to briefly talk about Tree Traversal and how it works. A Binary Tree traversal is the process of visiting each node in a given tree. there are several ways of traversing a tree and we will look at four general ways of doing so. let’s have them listed before we talk about them one after the other. We have two main categories for these operations BFS (Breath First Search) , DFS (Depth First Search).

BFS: in Breadth First Search we will talk about only one way of traversing the the tree by looking at it from it’s length perspective ie. let’s think of it as writing from left to right |————> not in arabic please. Left ——> Right I mean.

this search begins from the root node (Topmost) and run through all the nodes one by one following the mentioned approach above Left to Right, so at the end of the day the traces may look like a ZigZag line because after hitting the end of each left to right it comes back the next left side before visiting the right side. let’s how it works now

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insert(value) {
    let newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return this;
    }
    let 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;
      }
    }
  }
  
  BFS() {
    let node = this.root;
    let data = [];
    let 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;
  }
}

var tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
tree.BFS();

Up to the BFS Definition we only repeated our previous BST(Binary Search Tree) and performing a BFS on it should search and return all the nodes involved in the tree, here in our BFS we created two empty array variables one to mimic a queue, Remember we said in the last two previous section we are going to be using a queue and stack in the later structures ? well this is the time to bring our queue knowledge to play. in a queue we have a FIFO principle so here we’re going to turn our tree into queue to better do justice to each nodes in the tree. we equally create a data variable to push out elements to finally return as our found nodes, so the first thing to do is to push our root node into the queue because in BFS we start with the root node. While making sure the length of our queue is observed in order to jump out of the code we keep assigning the first element of the queue which we will later push its value into the data array to be return as our result. you can try make your own meaning out of the provided codes above.

Now let’s deal with the second category which is DFS(Depth First Search) this type of traversal is related to the depth of the tree conceptually from top to down from the left side to the down side and it can be achieved in three different ways: In-order Traversal, Pre-order Traversal, Post-order Traversal

In-order Traversal: with this type of traversal the root node is visited after the left side of the tree has been taken care of. ie Left Node(s)  —-> Root Node —->  Right Node(s) therefore the name in-order meaning the Root node should be inside the order of traversing tree. let’s code now

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insert(value) {
    let newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return this;
    }
    let 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;
      }
    }
  }
  
  DFSInOrder() {
    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;
  }
  
}

var tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
tree.DFSInOrder();

Same Song here as well we repeat the construction of the Binary Search Tree before implementing the DFSInOrder method and it a simple method not to forget, in the DFS we use recursion,  remember how we said recursion is just repeating the same function on a large problem after we split it into simple logics. So we created a function called traverse which will be called recursively on each node that is being visited, therefore a variable Data is created to collect all the pushed elements in the node that have been discovered. when we reach each left node we traverse and there after we  push the value involve until we get to the other right side we resume the  traverse recursion until all the nodes have been visited.

Pre-order Traversal: with this type of traversal the root node is visited first before the left side of the tree after which the right side will be visited. ie  Root Node —-> Left Node(s)  —->  Right Node(s) therefore the name pre-order meaning the Root node should be the first order of traversing the tree. let’s have the code now.

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insert(value) {
    let newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return this;
    }
    let 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;
      }
    }
  }
  
  DFSPreOrder() {
    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;
  }
  
}

var tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
tree.DFSPreOrder();

The first node is pushed then we keep visiting the left and right side through the traverse recursion function.

Post-order Traversal: in this last type of traversal obviously the Post means after so the root node is visited last after the left side of the tree and the right side have been visited. ie   Left Node(s)  —->  Right Node(s)—->Root Node therefore the name post-order meaning the Root node should be the last order of traversing the tree. let’s have the code now.

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insert(value) {
    let newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return this;
    }
    let 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;
      }
    }
  }
  
  DFSPostOrder() {
    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;
  }
  
}

var tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
tree.DFSPostOrder();

I beleive you can make your own meaning out of this one as well based on the hints above.

Observations: Notice how the output of the three DFS at each type the root Node positions itself exactly at where it should be depending on the type ie. in the inOrder the root node in the output is in the meddle of the returned result data, The PreOrder output will begin the result with the Root Node and the PostOrder will show a result that places the Root Node at the end of the List. Not All now taking a critical look at the in order you will observe the list has been fully sorted at the end of the inOrder Method. So you should now know what to use in the right context say for instance part of your requirement is to sort the list in the DFS then you should consider using the help of an In-Oerder DFS Traversal.

Once again I present to you my Baby language ideas on Tree Traversal, Do more research after this to affirm and rebind your understanding. Stay Safe 🙂