One Pager Cheat Sheet

• Proficiency in Breadth First Search (BFS) and Depth First Search (DFS) can greatly improve your ability to solve tree and graph problems found in software engineering interviews, and many seemingly unrelated challenges can be mapped as tree or graph problems.
• A tree is a hierarchical data structure with a root node and child nodes that can further have their own child nodes connected via edges, and nodes with no children are called leaf nodes.
• We can search a tree using two main techniques: Breadth First Search and Depth First Search which have different implementations and benefits.
• A tree node without any descendants or subtree is called a leaf node or terminal node.
• Breadth First Search (BFS) is a level-based traversal of a tree's nodes, typically from left to right, allowing for efficient traversal of the right-hand side of the tree.
• We can implement breadth first search to traverse a tree by adding nodes to a queue, popping items from the queue, printing or processing them, then adding their children to the queue, and repeating until the queue is empty.
• The breadth-first search algorithm is implemented in code as shown.
• Breadth-First Search (BFS) explores neighbor nodes before deeper nodes by navigating each layer of nodes and their neighbors in any order.
• We created a Tree_Node class and a method breadth_first_search(), which takes the root node as input and traverses the tree using BFS.
• We create a dictionary with keys and values corresponding to a tree's nodes, and use it to initialize a Tree_Node object whose value is the key of the first element and whose children are its corresponding values.
• We can traverse the tree using the breadth_first_search method by passing in the root node.
• You will see the expected sequence A, B, C, D, E, F, G, H, I, J in the output, followed by visiting the nodes in order 1, 2, 5, 3, 4, 6 in Python, JavaScript, C# and Java.
• It is recommended to use BFS in order to find the shortest path between two nodes in an unweighted graph, or when a solution is not far removed from the root of the tree, as opposed to using DFS in deeper trees with heuristics.
• Depth First Search (DFS) is a technique for traversing a tree that searches as deeply as possible before moving to neighbor nodes, done through three main methods, such as Preorder Traversal.
• By adding the left node last to the stack, Preorder Traversal DFS processes the left node first.
• The sample code in this article provides implementations of the Depth-First Search algorithm for Python, JavaScript, C#, and Java.
• The depth_first_search() method performs a Preorder Traversal BFS and can be tested using the example tree and its nodes.
• We are using In-Order Traversal to traverse the nodes using left-root-right logic in both Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms.
• The code outputted a matrix based on DFS algorithm and subsequently, followed a path visiting the elements in order from 1 to 6.
• When the tree is wide but with limited depth and when the need to detect a cycle arises, DFS is usually a better choice than BFS in terms of memory efficiency.
• BFS is the ideal algorithm for finding the shortest path between any two nodes in an unweighted graph, as it searches level by level and is therefore guaranteed to find the shortest path.