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

!!! CAN CLONE THE TREE !!!

    private TreeNode clone(TreeNode root){
        if(root==null){
            return null;
        }
        TreeNode node=new TreeNode(root.val);
        node.left=clone(root.left);
        node.right=clone(root.right);
        return node;
    }

AND SEARCH IN TREE

    private void doSearchBST(TreeNode node, int val) {
        if (node == null) {
            return;
        }

        if (node.val == val) {
            result = node;
        }
        doSearchBST(node.left, val);
        doSearchBST(node.right, val);
    }

// CHECK THIS, NOT SURE IF IT WORKS CORRECTLY
private TreeNode search(TreeNode cloned,TreeNode target){
        if(cloned==null){
            return null;
        }
        if(cloned.val==target.val){
            return cloned;
        }
        TreeNode a=search(cloned.left,target);
        if(a!=null){
            return a;
        }
        return search(cloned.right,target);
    }

Another example

    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

Algo.Java.DFS.Postorder

Another post order example

    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;
        }
        // do smth...
        return dfsPreorder(node.left, node.val) + dfsPreorder(node.right, node.val);
    }