Algo.Java.DFS.Theory

let’s say we have binary search tree like this

  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;
      }
  }

TRAVERSE PREORDER

    private void doSmth(TreeNode node) {
        //
    }
    
    public void dfsPreorder(TreeNode node) {
        if (node == null) {
            return;
        }
        doSmth(node);
        dfsPreorder(node.left);
        dfsPreorder(node.right);
    }

TRAVERSE INORDER

!!! GIVES A SORTED ORDER IN BINARY SEARCH TREE !!!

    private void doSmth(TreeNode node) {
        //
    }

    public void dfsInorder(TreeNode node) {
        if (node == null) {
            return;
        }

        dfsInorder(node.left);
        doSmth(node);
        dfsInorder(node.right);
    }

TRAVERSE POSTORDER

    private void doSmth(TreeNode node) {
        //
    }

    public void dfsPostorder(TreeNode node) {
        if (node == null) {
            return;
        }

        dfsPostorder(node.left);
        
        dfsPostorder(node.right);
        doSmth(node);
    }

SOME CONTAINER IN PARAM TO COLLECT VALUES FOR EXAMPLE

    public void dfsPreorder(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        list.add(node.val);
        dfsPreorder(node.left);
        dfsPreorder(node.right);
    }

PASS PREV PARAM TO COLLECT SUM, FOR EXAMPLE

    public int dfsPreorder(TreeNode node, int prev) {
        if (node == null) {
            return 0;
        }
        
        return dfsPreorder(node.left, node.val) + dfsPreorder(node.right, node.val);
    }