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   

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

.