Tree Traversal - DFS Intro

29 Dec 2021 in Algorithms

Tree Traversal had been so confusing to me for a while, but now I realized why it was more confusing than it had to be.

When I learnt about tree traversal such as Preorder, Inorder and Postorder traversal, The difference is ‘The order of visiting nodes’ . This is surely true,, Only when we just go through example with our head or paper.

Okay, so we know the basic. But… How do we actually implement this into code?

Normally in tree problems, root node is given, and relationship with other nodes are there already. What we do here is, we traverse all tree nodes from root to leaf by using .left or .right variable.

For example

/**
 * Definition for abinary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean RandomTreeProblem(TreeNode root) {
    //your code
    }
}

And Tree traversal in the code world, for most of DFS Tree Traversing code, the order of visiting nodes is actually the same and it’s going to be preorder traversal’s order for all of DFS problems that has a root node as an input. (Yeah mostly, we start traverse tree from the root and go left then right! since tree problems usually give root node as a input)

!!Each node is visited 4 times with this traversal.

1. node => left node

2. left node => node (pop)

3. node => right node

4. right node => node (pop)

The different point is the order of applying special treatment to each node,

'The order of visiting nodes is the same for all Traversal
Only the order of special treatment to nodes is different!'

In this example, the special treatment is ‘Print out values’.