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!
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:
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.
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
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.
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:
Phylogenetics (the study of the evolutionary history)
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:
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
Traversing a tree can either take a breadth-first or a depth-first approach.
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
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.
We have encountered trees in our Flatiron School curriculum. In the Hide and Seek lab, we traversed the DOM to find specific nodes using
deepestChild function can be easily amended to return the depth of the tree as opposed to just returning the deepest child.
Binary tree - Wikipedia
Binary Trees - Carnegie Mellon University
Girl Develop It, Intro to Algorithms