Depth of the first binary tree search

Question

I have an implementation of the first search depth algorithm:

public static void printDFS(Node root) { Stack<Node> stack = new Stack<Node>(); stack.push(root); while(!stack.isEmpty()) { Node curr = stack.pop(); System.out.println(curr.getValue()) ; if (curr.getLeft() != null) { stack.push(curr.getLeft()); } if (curr.getRight() != null) { stack.push(curr.getRight()); } } } 

and when I run it on a tree that looks like this:

  0 / \ 6 7 / \ / \ 5 4 3 2 

I get the result: 0 → 7 → 2 → 3 → 6 → 4 → 5

Is this the right choice for DFS? I would expect the result to be a preliminary traversal (i.e. 0 → 6 → 5 → 4 → 7 → 3 → 2), and I know that I can get this by first clicking on the right node of each subtree. But what do I want to know, what is the correct visit order in the DFS algorithm?

Answer 1

As mentioned in another answer , the reason your visit request is → "reverse" is because you use Stack to track the "current node".

Let me guide you through your example tree:

  0 / \ 6 7 / \ / \ 5 4 3 2 

stack.push(root) results in the following state of the stack:

 0: 0 <-- (root) and Top of stack 

You pop the stack and put it in curr . In terms of passing, you are in this state:

  0 <-- / \ 6 7 / \ / \ 5 4 3 2 

then go on to add curr.getLeft() to the stack and then curr.getRight() . This leads to the following state of the stack:

 1: 7 <--(curr.getRight()) <-- Top of stack 0: 6 <--(curr.getLeft()) 

Repeating the same step, we get the following workaround:

  0 / \ 6 7<-- / \ / \ 5 4 3 2 

and after adding nodes:

 2: 2 <-- Top of stack 1: 3 0: 6 <-- (initial getLeft()) 

since both nodes have no children, pushing them out of the stack, and outputting them leads us to the following workaround:

  0 / \ -->6 7 / \ / \ 5 4 3 2 

The rest is history;)

As you specifically asked about the “right” way (or order) for DFS: it is not. You determine which side you go first in depth.

Answer 2

There is no such “proper DFS ordering”. The main idea of ​​DFS is to go deep; visiting children in front of brothers and sisters for any given node. Once you go deep into the chart and you come across a sheet, you go back and examine your nearest brother in the same way.

How do you choose which child should examine the first result in different orders of movement (or trees). Needless to say, all move methods lead to the creation of a spanning tree above the graph. Going through the pre-order with which you are comparing is probably the best known order for DFS (or at least this is what I saw). Others are valid but not very popular.

Answer 3

This is a stack. The last thing you click will appear first

Answer 4

Here is the pseudo code for DFS:

'' "This is more of a crawl algorithm than a search. '' '

 Algorithm DFS(Tree): initialize stack to contain Tree.root() while stack is not empty: p = stack.pop() perform 'action' for p for each child 'c' in Tree.children(p): stack.push(c) 

This will be a search on all nodes of the tree, whether binary or not. To implement search and return .. modify the algorithm accordingly.

Answer 5

There are several options for your DFS algorithm:

• First, use the Backtracking algorithm to search for DFS.
• When using Backtracking add only leftChild while moving down. Otherwise, change the order in which you push() children node to the right Stack ie rightChild , and then leftChild .
• Again, if you use Backtracking , avoid loops by creating a nodeVistited variable that will be set to true after the node is pushed onto the stack. Otherwise not required. Try with these changes or let me know I will send the code for DFS.