During the junior developer panel at Flatiron School, when asked about typical interview questions, one of the panelists mentioned that they were asked to “write a function that gets the depth of a tree.” I hear and read about trees often and I don’t really know what they are, so I thought this was a good opportunity to learn a little bit about trees!
Trees in Cracking The Coding Interview
On page 47 (10% into the book) of Cracking the Coding Interview, Gayle Laakmann McDowell outlines the “absolute must have basics” of data structures and algorithms to know for an interview:
Caveats
I want mention that while this book is really useful and comprehensive, it is seemingly geared toward the “Stanford Big Four” set - kids who graduated from Stanford and are vying to work at Google, Facebook, Apple, or Microsoft. That’s not my lifestyle or what I’m interested in, but in any case it’s a very interesting book, and it’s good to know what Silicon Valley is expecting. As we heard in the junior developer panel, it’s likely that you will be asked CS questions during the interview process.
Tree basics
As an introduction, my goal for this post is to share:
- definitions and differences between tree and binary tree data structures
- real life examples of general trees
- overview of two techniques to traverse a tree
What a tree is not
A tree is not a linearly organized data structure, like an array or a linked list. A data structure is said to be linear if its elements form a sequence. A hash is also not a linearly organized data structure because its order of return cannot be guaranteed.
General trees
A general tree is a data structure with nodes. There is no limit on the degree of nodes in a general tree, and each node can have an infinite number of children.
Real life examples of general trees:
The DOM
Phylogenetics (the study of the evolutionary history)
Binary trees
A binary tree is a data structure in that each node has at most two nodes: left and right.
Real life examples of binary trees:
Family tree
Advantages of trees
Trees are useful and frequently used because they have some advantages:
- Trees reflect structural relationships in the data
- Trees are used to represent hierarchies
- Trees provide an efficient insertion and searching
- Trees are very flexible data, allowing to move subtrees around with minimum effort
Techniques for traversing a tree
Traversing a tree can either take a breadth-first or a depth-first approach.
Breadth first search
Explores the neighbor nodes first, before moving to the next level neighbors.
There are three different types of depth-first traversals:
- PreOrder traversal - visit the parent first and then left and right children
- InOrder traversal - visit the left child, then the parent and the right child
- PostOrder traversal - visit left child, then the right child and then the parent
Depth first search
Explores all the children of a neighboring node before moving to the next neighbor and its children.
There is only one kind of breadth-first traversal:
- Level order traversal. This traversal visits nodes by levels from top to bottom and from left to right.
Simple tree example in our Flatiron School curriculum
We have encountered trees in our Flatiron School curriculum. In the Hide and Seek lab, we traversed the DOM to find specific nodes using document.querySelector() and document.querySelectorAll(). The deepestChild function can be easily amended to return the depth of the tree as opposed to just returning the deepest child.
Reference
Binary tree - Wikipedia
https://en.wikipedia.org/wiki/Binary_tree
Data Structures With JavaScript: Tree
https://code.tutsplus.com/articles/data-structures-with-javascript-tree--cms-23393
Binary Trees - Carnegie Mellon University
https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html
Girl Develop It, Intro to Algorithms
http://www.teaching-materials.org/algorithms/#/
The DOM Is A Tree
https://learn.co/tracks/web-development-immersive-winter-2016/javascript/the-dom/the-dom-is-a-tree