DEV Community

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

Posted on • Originally published at blog.abmsourav.com

2 2

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

.

AWS Q Developer image

Your AI Code Assistant

Automate your code reviews. Catch bugs before your coworkers. Fix security issues in your code. Built to handle large projects, Amazon Q Developer works alongside you from idea to production code.

Get started free in your IDE

Top comments (0)

Billboard image

Create up to 10 Postgres Databases on Neon's free plan.

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Try Neon for Free →

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay