Tree traversals

 I have the first phase of the interviewing process with Audatic https://audatic.ai/ The first phase are timed coding exercises through their custom web app. I am going to do it over the holidays! I am really looking forward to it!

I bought myself an AlgoExpert subscription https://www.algoexpert.io/ over the Black Friday and they've got Mock Interviews! I need those things so badly! I tried to do mock interviews with Pramp https://www.pramp.com/#/ but it was too tough, because they didn't have a pool of questions that you could prepare for. The problems were so mega difficult! On AlgoExpert the question you get comes from the pool of problems (with full video tutorials on the site). Basically, you could just memorize all the questions:-D It gives me a sense of security that I need while I'm still practicing. So far I've completed 16 interview questions and there's 110 of them:-D

Anyway, I have a scheduled mock interview this evening and the coding question for my partner is finding the longest path in a binary tree (called the diameter). The first thing I thought of was depth first search and yep, that's the algorithm in the solution video. You do a depth first search on every node of the tree.

Which brings me to the topic of the post: getting friends with tree traversals. This post is based on this post which is ever-so wonderful https://medium.com/@nhudinhtuan/binary-tree-traversals-cheat-sheet-for-coding-interviews-a71af9fe1dba I have to admit. Tree problems have been hard for me. There was a question on AlgoExpert about implementing a BST (binary search tree) class with all the data structure operations (for example the very tough delete node operation) and I still haven't finished it. And when I saw the different tree traversal methods I was like HTF am I supposed to understand and remember them? It was tough. Fortunately, this post is super clear and has everything that I need!

So DFS (depth-first search)! The idea is to go down a path as far as possible before back tracking, hence the name depth first. Imagine you're a student and  you're trying to master the tree of human knowledge. Depth first search strategy would correspond to specializing intensely. You study biology, then you specialize in molecular cell biology, then you study a particular system, then you focus on just one molecule or gene etc. Breadth first search explores a graph in layers, this would mean you would learn a bit of biology, a bit of math, a bit of computer science, a bit of music theory... I'm definitely a breadth first search:-D You know, there's also hybrid methods like A*-search where you balance exploration and exploitation by balancing the depth first and breadth first approach.

Anyway, depth first search is an in-order traversal. And it can be implemented using either recursion or a stack data structure. In the stack data structure you place and retrieve items as though you were laying on a pile of books. You keep stacking up books and you always retrieve the top one, the one you stacked up last. That's why it's called LIFO-- last in first out. 

In the version of in-order traversal that is used in the medium post-- you start from the root and you just keep going left as far as you can go, filling up a stack as you go. And when there's nothing more to add, you start popping the stack. I want to burn it into my head, in-order traversal:: depth first search:: working with a stack:-) Here's some code I wrote and adapted: https://github.com/mariakesa/Algorithms/blob/master/AlgoExpert/AlgoExpertQuestions.ipynb Check under Binary Tree Diameter:-)

Just a quick post here, hope the medium post link might be useful to somebody!