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 visual representation of DFT algorithm on a Binary tree.

You must be thinking, ‘why is it going to the last left node?’

The answer is, that’s why it’s DFT. DFT always focuses on the depth of the DS. If we access level-by-level, then it’ll become a Breadth-First Traverse. I’ll write another article on BFT very soon.

Two things are very important in DFT.
1. “If the next node is null” — If it’s true then DFT starts going backward. Meaning it starts going back to the root.
2. The iteration will end when the stack will become empty.

Pre Order

DFT types are different from each other for their data access pattern. For example PreOrder DFT data access pattern is Root, Left, Right.
The above visual example is a PreOrder DFT.

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.

Code Example:

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))
// [ 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	

In Order

The data access pattern is Left, Root, Right. Let’s see a visual representation…

What’s happening here:

• Access the root node, put it in the stack.
• Then “if the next left node is not null” then, put its next left node in the stack. But “if null” then bring the last item from the stack.
• Bring the last item from the stack, which is the last left node.
• Then printed its data.
• Then bring the last item of the stack, which is the parent node of the previously printed node.
• Then Print its data, then put its right node to the stack.
• Keep doing the above, till the stack is not empty.

Code Example:

const dft_inOrder = (root) => {
	const list = []
	
	function dftRecursion(root) {
		if (!root) return list

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

		return list
	}
	dftRecursion(root)

	return list

}

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

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

Post Order

The Data access pattern is Left, Right, Root. Let’s see a visual representation…

What’s happening here:

• Access the root node, put it in the stack.
• 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.
• Then go to the last item of the stack, which is the parent node of the previously printed node.
• Then go to its right node, put it in the stack, then bring it from the stack.
• If its next nodes are null then print its data. Otherwise, keep adding to the stack till the last node.
• Keep doing the above, till the stack is not empty.

Code Example:

const dft_postOrder = (root) => {
	const list = []
	
	function dftRecursion(root) {
		if (!root) return list

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

		return list
	}
	dftRecursion(root)

	return list

}

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

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