DFS vs BFS

 DFS vs BFS

There are two ways to traverse the tree: DFS depth first search and BFS breadth first search. Here is a small summary

diff

Let's use this problem to discuss the difference between iterative BFS traversal with the queue and iterative DFS preorder traversal with the stack.

Both start from the root and go down, both use additional structures, what's the difference?

Here is how it looks at the big scale: BFS traverses level by level, and DFS first goes to the leaves.

diff

Now let's go down to the implementation. The idea is similar:

  • Push root into queue (BFS) or stack (DFS).

  • At each step pop out one node, and push its children into stack/queue.

For BFS: pop out from the left, first push the left child, and then the right one.

For DFS: pop out from the right, first push the right child, and then the left one.

diff

Comments

Post a Comment

Popular posts from this blog

Java 8 : Find the number starts with 1 from a list of integers

  List<Integer> list = List. of ( 12 , 32 , 14 , 15 , 56 ); //Result->12,14,15 List<String> listString = list.stream().map(String::valueOf).collect(Collectors.toList()); List<String> result1 = listString.stream().filter(x->x.startsWith( "1" )) .collect(Collectors.toList()); System. out .println( "result1-->" +result1); List<String> result2 = list.stream().map(x->x+ "" ).filter(x->x.startsWith( "1" )) .collect(Collectors.toList()); System. out .println( "result2-->" +result2);
Read more

How to prevent Singleton Class from Reflection and Serialization

Image
First create a singleton class. If we will try to clone it, it will throw Exception.  Now try to break the Singleton with Reflection How to prevent Object Creation with Reflection - Check in the private constructor if object already created then throw an exception. If we run the reflection code, we will get this exception. Prevent Singleton Class from Serialization We have to override the read resolve method
Read more

Optional Vs Null Check

Image
The purpose of Optional is not to replace every single null reference in your codebase but rather to help design better APIs in which—just by reading the signature of a method—users can tell whether to expect an optional value. In addition, Optional forces you to actively unwrap an Optional to deal with the absence of a value; as a result, you protect your code against unintended null pointer exceptions. String version = computer.getSoundcard().getUSB().getVersion(); This code can lead to NullPointerException. Handle NullPointerException - This code looks ugly. String version = "UNKNOWN"; if(computer != null){   Soundcard soundcard = computer.getSoundcard();   if(soundcard != null){     USB usb = soundcard.getUSB();     if(usb != null){       version = usb.getVersion();     }   } } String name = computer.flatMap(Computer::getSoundcard)                           .f...
Read more