Practice 30 Google Software Developer interview questions covering algorithms, system design, and coding challenges.
Question 7 of 30
How to Answer
Example Answer
Community Answers

William Swansen has worked in the employment assistance realm since 2007. He is an author, job search strategist, and career advisor who helps individuals worldwide and in various professions to find their ideal careers.
When looking at a question of this magnitude, there are several different factors to consider. You will want to get clarification from the Google interviewer on whether they want to hear the meaning for tree structure data, time complexity, extra space, or a node stack. Let's examine what some of these mean and how they might come up in the course of an interview. Time Complexity - has four transversals O(n) as they visit every node exactly once. Extra space - requires O(w) Level Order Transversal where w is the maximum width of a Binary Tree which stores nodes of different levels.

William Swansen has worked in the employment assistance realm since 2007. He is an author, job search strategist, and career advisor who helps individuals worldwide and in various professions to find their ideal careers.
"I'm familiar with the meaning of this question. There are a couple of ways to answer it, so I will give you both examples. The two most common methods of searching a graph or a tree related to a depth-first search are depth-first search and breadth-first search, for starters. Depending on the application you are using and the result you want to achieve, this should be determined by the type of data in your tree or graph data structure. For a Breath First Search, I start at the root node. I then search all their children nodes moving from left to right, then I repeat the process at the level below the root node. I typically repeat this on each level until I reach the end of the tree or node. As a general practice, I use a queue as an intermediary step as a way of keeping track of what nodes I need to search."

Interview Coach
Jaymie
A real coach, not AI. I read every answer myself and write back with personalized feedback.
Typically responds within 24 hours.
0 - Character Count
Prepare with questions that reflect Google's rigorous technical interview process.
Get StartedJump to Question

Written by William Swansen
30 Questions & Answers • Google

By William

By William