DEV Community

Cover image for Depth First Traverse
Keramot UL Islam
Keramot UL Islam

Posted on • Originally published at blog.abmsourav.com

Depth First Traverse

Depth First is an algorithm that traverses data structures focusing on the depth of nodes. It is useful for searching data in a DS or adding or updating data in the nth place of a DS.

There are Three types of DFT [Depth First Traverse]

  1. Pre Order
  2. In Order
  3. Post Order

Now let’s see a code example of DFT algorithm on a Binary tree.

const dft_preOrder = (root) => {
    const list = []

    function dftRecursion(root) {
        if (!root) return list

        list.push(root.val) // pre order
        dftRecursion(root.left)
        dftRecursion(root.right)

        return list
    }
    dftRecursion(root)

    return list

}

console.log(dft_preOrder(binaryTree))
// result: [ 1, 2, 4, 5, 3, 4, 6 ]

// put a binary tree as the root parameter. 
// It looks like this:
//            1
//          /   \
//         2      3
//        / \    / \
//       4   5  4   6   
Enter fullscreen mode Exit fullscreen mode

So, What’s happening here:

  • Access the root node, put it in the stack, then pop from the stack
  • Printed its data.
  • Then “if next nodes are not null” then, put its next right and left nodes in the stack. But “if null” then bring the last item from the stack.
  • Bring the last item from the stack, which is the left node.
  • Then printed its data.
  • Keep doing the above, till the stack is not empty.

Read the full article to know more about all types of Depth First Traverse using animations on my blog. Click Here

.

Top comments (0)