# 🔥 Tree DFS (Depth-first-search) in javascript

## ✨ Recursive Algorithm

``````let res = 0;

const dfs = (node) => {
if (!node) return;

// pre-order
dfs(node.left);
// in-order
dfs(node.right);
// post-order
};

dfs(root);

return res;
``````

### ⬇️ pre-order : top-down traversal from top to bottom

#### Question

• Can you determine some parameters to help the node know its answer?
• Can you use these parameters and the value of the node itself to determine what should be the parameters passed to its children?
``````const dfs = (node) => {
if (!node) return;

// pre-order
dfs(node.left);
dfs(node.right);
};
``````
• In preorder traversal, logic is done on the current node before moving to the children.
• Let's say that we wanted to just print the value of each node in the tree to the console.
• In that case, at any given node, we would print the current node's value, then recursively call the left child, then recursively call the right child (or right then left, it doesn't matter, but left before right is more common).

### in-order

``````const dfs = (node) => {
if (!node) return;

dfs(node.left);
// in-order
dfs(node.right);
};
``````
• For inorder traversal, we first recursively call the left child, then perform logic (print in thise case) on the current node, then recursively call the right child.
• This means no logic will be done until we reach a node without a left child since calling on the left child takes priority over performing logic.

### ⬆️ post-order : bottom-up traversal from bottom to root

#### Question

• If you know the answer of its children, can you calculate the answer of that node?
``````const dfs = (node) => {
if (!node) return;

dfs(node.left);
dfs(node.right);
// post-order
};
``````
• We recursively call on the children first and then perform logic on the current node.
• This means no logic will be done until we reach a leaf node since calling on the children takes priority over performing logic.
• In a postorder traversal, the root is the last node where logic is done.

## ✨ Iterative Algorithm

``````const dfs = (root) => [
const stack = [ roote ];
let res = 0;

while (stack.length) {
const node = stack.pop();

// do some logic

if (node.left) stack.push(node.left);
if (node.right) stack.push(node.right);
}

return res;
]

return dfs(root);
``````