DFS with Stack

BinaryTree를 DFS(depth first search)하기에는 recursion이 간편하다.

하지만 recursion 없이 stack을 이용하는 방법도 있는데, java코드로 표현하면 다음과 같다.

 

 

static void printDFS(Node node) {

        Stack<Node> stack = new Stack<>();

        Node temp = node;
        while (temp != null || !stack.isEmpty()) {

            //(THIS + Left)푸쉬 => left,this,right 출력.
            while (temp != null) {
                //this push
                stack.push(temp);
                //left traverse
                temp = temp.left;
            }

            //start print
            temp = stack.pop();
            print(temp); /////////////////////////////////////

            //right point : goto TOP
            temp = temp.right;
        }
    }